На бесконечной шахматной доске на первой горизонтали стоит особая пешка. она может ходить только вверх, причём, либо на 2 клетки, либо на 1. сколькими она может добраться до 13-ой горизонтали?
Чтобы решить данную задачу, мы можем воспользоваться методом динамического программирования.
1. Начнем с составления таблицы, в которой будем отслеживать количество способов достижения каждой горизонтали до 13-ой.
Назовем эту таблицу dp, и размерностью 14 (первая строка – горизонтали от 0 до 13).
2. Так как пешка может двигаться либо на 2 клетки, либо на 1, заполним первые 2 ячейки таблицы:
dp[0] = 0 (пешка стоит на первой горизонтали, значит, способов достичь ее нет)
dp[1] = 1 (пешка может переместиться вперед на одну клетку)
3. Далее, заполним таблицу с третьей горизонтали до 13-ой, используя рекуррентную формулу:
dp[i] = dp[i-1] + dp[i-2], где i > 1
В данной формуле dp[i-1] обозначает количество способов достичь горизонтали i-1, а dp[i-2] – количество способов достичь горизонтали i-2.
Таким образом, мы суммируем количество путей до i-1 и i-2 горизонталей, так как пешка может переместиться либо на 1, либо на 2 клетки.
4. Продолжаем заполнять таблицу до 13-ой горизонтали, используя рекуррентную формулу из предыдущего пункта:
dp[i] = dp[i-1] + dp[i-2]
5. В итоге, значение dp[13] будет показывать количество способов, которыми пешка может достичь 13-ой горизонтали.
