UniLecs #184. Ступеньки

Задача: вы поднимаетесь по лестнице, и вам необходимо сделать N шагов, чтобы добраться до вашего этажа. Каждый раз вы можете сделать либо 1, либо 2 шага.

Посчитайте, сколько всего различных способов у вас есть, чтобы сделать это.

Входные данные: N - натуральное число от 1 до 100.

Вывод: кол-во различных способов.

Пример: 

1. N = 2;

Answer = 2 (1 + 1 шага; 2 шага)

2. N = 3;

Answer = 3 (1 + 1 + 1 шага; 1 + 2 шага; 2 + 1 шага)

Идея:

Рекурсия с мемоизацией.

В подходе с рекурсией мы принимаем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге. 

И на каждом шаге мы вызываем функцию для шагов 1 и 2 и возвращаем сумму возвращенных значений обеих функций.

Для оптимизации рекурсии мы воспользуемся подходом с запоминанием результатов, так называемая мемоизация.

Динамика или последовательность Фиббоначи.

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

Т.е. достичь i-й ступеньки можно 2мя способами:

1. Сделать 1 шаг со ступеньки (i-1).

2. Сделать 2 шага со ступеньки (i-2).

Поэтому получаем, что кол-во вариантов достижения iй ступеньки равно сумме вариантов достижения (i-1)й ступеньки и вариантов достижения (i-2)й ступеньки.

Отсюда получаем формулу для iй ступеньки, пусть dp[i] - количество способов достичь i-го ступеньки i.

dp[i] = dp[i - 1] + dp[i - 2]

Если хорошенько присмотреться, то можно увидеть формулу получения iго члена последовательности Фибоначчи. Поэтому наш подход с динамическим программированием трансформируется в задачу нахождения iго члена последовательности Фибоначчи.

Реализация:

https://gist.github.com/unilecs/dcfcffbc3de28d0d2683957a83cc08c2

Play-test: https://dotnetfiddle.net/V0Hk6g