Сложность: easy
Чтобы добраться до вершины лестницы с n ступенями, можно каждый раз делать шаг на 1 или 2 ступеньки.
Нужно посчитать, сколькими способами можно подняться на вершину.
Пример:
Input: n = 2 Output: 2
Варианты:
1 + 1
2
👨💻 Алгоритм:
1⃣На каждом шаге есть 2 варианта: подняться на 1 или на 2 ступеньки — задача сводится к подсчёту всех таких комбинаций
2⃣Используем рекурсивную функцию:
climb(i, n) = climb(i + 1, n) + climb(i + 2, n) — сумма способов дойти с текущей позиции i до цели n
3⃣Базовые случаи:
если i == n — достигли цели, вернуть 1
если i > n — вышли за пределы, вернуть 0
😎 Решение:
class Solution {
public:
int climbStairs(int n) { return climb_Stairs(0, n); }
int climb_Stairs(int i, int n) {
if (i > n) return 0;
if (i == n) return 1;
return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}
};Ставь 👍 и забирай 📚 Базу знаний