Код Junior Динамическое программирование обновлено
Варианты подъёма по лестнице
Условие
Сколько способов подняться на n ступеней шагами по 1 или 2?
Примеры
climbStairs(2) // 2
climbStairs(3) // 3
climbStairs(1) // 1
Как подойти
Рекуррента dp[i] = dp[i-1] + dp[i-2]. Достаточно двух переменных - O(1) памяти. Умение свернуть массив ДП до пары переменных - то, что отличает разобранное решение от заученного.
Подсказки: 2
- Число способов дойти до ступени n - сумма способов дойти до n-1 и n-2.
- Это Фибоначчи со сдвигом.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.