Удаление объектов K так, что нет двух соседних

Question

Есть 2 ряда, соединенных бок о бок с n объектами в каждом ряду.Каково количество способов удаления ровно k объектов, чтобы после удаления не было двух свободных мест рядом друг с другом.

, например.когда n = 4, k = 2 - 18, когда n = 5, k = 3 - 50.

Я не могу получить формулу для ее решения при любом значении n, k (k<= 2 * n). <a href="https://i.stack.imgur.com/piBcf.jpg" rel="nofollow noreferrer"> изображение соединения двух строк

Answer 1

Посмотрите на эту рекурсивную функцию.Он рассчитывает количество вариантов для данного флага n, k и last (показывает, помечали ли мы ячейку в последнем столбце).

Если мы не помечаем ячейку в текущем столбце, у нас есть три варианта следующего: не отмечать снова, отмечать сверху, отмечать снизу.

Если мы помечаем ячейку в текущем столбце, у нас есть только два варианта для следующего: не отмечать снова или отмечать ячейку в противоположной строке.

Обратите внимание, что код возвращает правильный результат 38 для вашего второго примера - есть C(5,3)=10 комбинации для распределения объектов по столбцам.Одиночная комбинация с разделенными столбцами 10101 дает 8 вариантов, три комбинации с объединенными столбцами, например 01110, дают 3 * 2 = 6 вариантов, а шесть комбинаций, таких как 01011, дают 6 * 4 = 24 варианта.

Предоставленный код не эффективен (он имеет экспоненциальную сложность), поэтому для практических целей его следует переписать с использованием динамического программирования или запоминания (сохранение результатов вызовов в карте с помощью клавиши n / k / l и их повторное использование при необходимости) или с использованием табличного подхода(заполните н / к / л таблицу по ячейкам).

Я оставляю это преобразование как довольно простое упражнение для автора (потому что автор не показал никакого собственного кода)

def F(n, k, last):
    if k > n:
        return 0
    if k == 0:
        return 1
    if k == n:
        return 2 - last         # 2 if last==0 else 1

    return F(n - 1, k, 0) + (2 - last) * F(n - 1, k - 1, 1)

print(F(4,2,0))
print(F(5,3,0))

>>18
>>38