Поколение Python 🐍

Друзья, давайте разберем вчерашние задачи. 🪜



Общий подход к решению таких задач называют динамическим программированием. Он заключается в том, что мы делим решаемую задачу на более мелкие подзадачи. Решив их, мы можем построить ответ и для задачи побольше.



Сначала поговорим про первую задачу. На i-ую ступеньку мы можем попасть только в том случае, если совершим прыжок на 1 ступеньку вверх с (i-1)-ой ступеньки или совершим прыжок на 2 ступеньки вверх с (i-2)-ой ступеньки.



Введем функцию f(n), которая будет равна количеству способов добраться до n-ой ступеньки. Тогда из соображений выше получаем рекуррентную формулу: f(n) = f(n-1) + f(n-2).



К примеру, чтобы добраться до 7-ой ступеньки, мы должны либо совершить прыжок с 6-ой ступеньки, либо совершить прыжок с 5-ой ступеньки. Тогда количество способов добраться до 7-ой ступеньки равно сумме количеств способов добраться до 5-й ступеньки и до 6-й ступеньки.



Начиная с n = 2, мы можем последовательно вычислять значения данной функции. Формально изначально Кемаль находится на 0-й ступеньке и f(0) = 1, несложно догадаться, что тогда f(1) = 1. Далее находим f(2) = f(0) + f(1) = 2, f(3) = f(1) + f(2) = 3, f(4) = f(2) + f(3) = 5, f(5) = f(3) + f(4) = 8, f(6) = f(4) + f(5) = 13, f(7) = f(5) + f(6) = 21.



P.S. Особо внимательные заметили, что рекуррентная формула для вычисления ответа на задачу в точности совпадает с рекуррентной формулой для подсчета n-го числа Фибоначчи.



Теперь можем приступить к решению второй задачи. Аналогично первой, можем составить рекуррентную формулу: f(n) = f(n-1) + f(n-2) + f(n-4).



Начиная с n = 4, мы можем пользоваться данной формулой. Несложно догадаться, что f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3. Тогда f(7) = 31.



#разборазадачи