Задача с фронтенд Яндекс.

Вы находитесь на левой верхней клетке шахматной доски и хотите добраться до правой нижней. У вас есть возможность двигаться вправо, вниз и по диагонали вниз. При этом запрещено три раза подряд перемещаться по клеткам одного цвета.

Сколько существует путей, чтобы попасть из левой верхней клетки в правую нижнюю?

Решение:
Заметим, что при движении по диагонали вниз мы всегда попадаем на клетки одинакового цвета. Следовательно, мы не можем двигаться по диагонали более одного раза подряд.

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

Пусть dp[i][j][0] обозначает количество способов добраться до позиции (i, j), при этом последнее движение было вправо или вниз. А dp[i][j][1] — количество способов, когда последнее движение было по диагонали.

В таком случае в позицию (i, j, 0) мы можем попасть из следующих позиций:

(i-1, j, 0); (i-1, j, 1);
(i, j-1, 0); (i, j-1, 1).

А на позицию (i, j, 1) мы можем попасть только из (i-1, j-1, 0).

Теперь, когда мы понимаем все переходы и состояния динамического программирования, ответом будет сумма dp[n-1][n-1][0] и dp[n-1][n-1][1].
Код в комментариях:


Эта задача была на контесте яндекса. Больше разбора для тех кто взял курсы.

@algoses