В общем, нужен алгоритм к задаче, которая написана внизу.
Вот моя идея : идея за O(N^2)
, база динамики dp[0][0] = 1
, и потом просто бежим по клеткам, и в каждую клетку записываем сумму значений клеток, из которых мы можем попасть в эту клетку, т.е dp[i][j] = dp[i - 2][j - 1] + dp[i - 2][j + 1]
...
И это не работает. Я даже знаю почему, но не знаю, как это исправить.
Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только : на 2 клетки вправо и на одну либо вверх, либо вниз, или на 2 клетки вниз и на одну либо вправо, либо влево.
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Формат входного файла
В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15).
Формат выходного файла
В выходной файл выведите единственное число количество способов добраться конём до правого нижнего угла доски.
Вх. данные Выход 15 14 7884330