Количество кратчайших путей с условием, подскажите хотя бы идею Сколько различных кратчайших путей ведут из левого нижнего угла в правый верхний угол прямоугольника 16 на 13 клеток? Сколько будет путей если два вертикальных участка не могут идти подряд
Первое я вроде решил методом динамического программирования, а со вторым проблемы. Можете подсказать идею реализуемую на любом языке программирования (нужна только идея)

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи с ограничением на вертикальные участки, можно использовать метод динамического программирования с дополнительным условием.

В начале, как и в обычном случае, мы заполняем таблицу путей для каждой клетки, указывая количество способов достижения этой клетки из начальной клетки.

Далее, для каждой клетки, где два вертикальных участка идут подряд, мы обнуляем количество путей, которое ведет к этой клетке.

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

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