Сложность: easy
Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек.
Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины?
Пример:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
👨💻 Алгоритм:
1⃣В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге.
2⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций.
3⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг.
😎 Решение:
func climbStairs(_ n: Int) -> Int {
return climbStairsHelper(0, n)
}
func climbStairsHelper(_ i: Int, _ n: Int) -> Int {
if i > n {
return 0
}
if i == n {
return 1
}
return climbStairsHelper(i + 1, n) + climbStairsHelper(i + 2, n)
}Ставь 👍 и забирай 📚 Базу знаний