На бесконечной шахматной доске на первой горизонтали стоит особая пешка. она может ходить только вверх, причём, либо на 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-ой горизонтали.
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-ой горизонтали.
Итак, заполним таблицу:
dp[0] = 0
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1 + 0 = 1
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp[4] = dp[3] + dp[2] = 2 + 1 = 3
dp[5] = dp[4] + dp[3] = 3 + 2 = 5
...
dp[13] = dp[12] + dp[11] = 233 + 144 = 377
Таким образом, пешка может достичь 13-ой горизонтали с помощью 377 разных путей.