← Назад к ДП

Подъём по ступенькам

Количество способов подняться на n ступенек (шаги 1, 2 или 3)

🐍 Python (рекурсия + мемоизация)
def climb(n, memo={}):
    if n <= 0:
        return 1 if n == 0 else 0
    if n in memo:
        return memo[n]
    memo[n] = climb(n-1) + climb(n-2) + climb(n-3)
    return memo[n]

n = int(input())
print(climb(n))
⚙️ C++ (рекурсия + мемоизация)
#include <bits/stdc++.h>
using namespace std;

vector<long long> memo;

long long climb(int n) {
    if (n <= 0) return (n == 0) ? 1 : 0;
    if (memo[n] != -1) return memo[n];
    return memo[n] = climb(n-1) + climb(n-2) + climb(n-3);
}

int main() {
    int n;
    cin >> n;
    memo.assign(n + 1, -1);
    cout << climb(n) << endl;
    return 0;
}
🐍 Python (DP — итеративный)
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
     dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
print(dp[n])
⚙️ C++ (DP — итеративный)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    cout << dp[n] << endl;
    return 0;
}

Как работает подъём по ступенькам?

Задача: найти количество способов подняться на n-ю ступеньку, если за один шаг можно подняться на 1, 2 или 3 ступеньки.

Основная идея динамического программирования:

Базовые случаи:

Рекурсия с мемоизацией (top-down): начинаем с n и рекурсивно спускаемся, запоминая результаты.

Итеративный DP (bottom-up): заполняем массив от 0 до n, последовательно вычисляя каждое значение.

Временная сложность: O(n) — каждое значение вычисляется один раз.

Пространственная сложность: O(n) для массива dp или O(1) для оптимизированного варианта (хранить только три последних значения).

Формат ввода и вывода

Ввод:

Вывод:

Пример ввода:

4

Вывод: 7

Способы подняться на 4-ю ступеньку (1,2,3 шага):
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 — всего 7 способов.

Попробовать онлайн

Введите номер ступеньки:

Результат появится здесь...