Python Рекурсия
Есть задача: Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до n слева направо. В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть на следующий столбик или сразу на второй столбик, считая от текущего.
Найдите количество способов, которыми Кузнечик может добраться до столбика с номером n. Учитывайте, что Кузнечик не может прыгать назад.
Внимание! Данная задача должна решаться рекурсией. Вы не можете использовать циклы
Тесты:
входные данные
3
выходные данные
2
входные данные
4
выходные данные
3
входные данные
45
выходные данные
1134903170
Как это решить рекурсией а не циклами???
Ответы (1 шт):
Cкорее всего, требуется использование "ленивого" ДП: вы пишете самое глупое решение через рекурсию: f(n) = f(n - 1) + f(n - 2), f(1) = 1, f(2) = 1 и добавляете внешний массив dp[MAXN+1], в который записываете ответы для каждого рассчитанного на данный момент n.
Без использования дополнительной памяти, можно просто переписать цикл в рекурсию, но это уже извращение.
def f(n):
global dp
if dp[n] != -1:
return dp[n]
dp[n] = f(n - 1) + f(n - 2)
return dp[n]
dp = [-1] * 46
dp[0], dp[1] = 0, 1