70. Climbing Stairs

Задача

Лестница из n ступеней. За раз можно подняться на 1 или 2 ступени. Сколькими способами можно достичь вершины?

Примеры

Пример 1

Input: n = 2
Output: 2

Пояснение

Два способа: 1+1 или 2.

Пример 2

Input: n = 3
Output: 3

Пояснение

Три способа: 1+1+1, 1+2, 2+1.

Решение

Решение

/**
 * Временная сложность: O(n)
 * Пространственная сложность: O(1) - храним только 2 переменные
 */
var climbStairs = function(n) {
    if (n <= 2) return n;
 
    let prev2 = 1; // Способов для n-2 (для 1-й ступеньки)
    let prev1 = 2; // Способов для n-1 (для 2-й ступеньки)
 
    for (let i = 3; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
 
    return prev1;
};

Доп. функция для разного количества шагов

/**
 * Climbing Stairs - Обобщенное решение
 * 
 * Время: O(n * k), где n - количество ступенек, k - максимальный размер шага
 * Память: O(n) для массива dp
 * 
 * Логика:
 * - dp[i] = количество способов достичь ступеньки i
 * - Для каждой ступеньки суммируем способы со всех возможных предыдущих позиций
 * - dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]
 */
function climbStairs(n: number, maxStep: number): number {
    // Массив для хранения количества способов для каждой ступеньки
    const dp = new Array(n + 1).fill(0);
 
    // Базовый случай: 1 способ остаться на земле (0 ступенек)
    dp[0] = 1;
 
    // Проходим по каждой ступеньке от 1 до n
    for (let i = 1; i <= n; i++) {
        // Проверяем все возможные размеры шагов (1, 2, 3, ..., maxStep)
        for (let step = 1; step <= maxStep && step <= i; step++) {
            // Добавляем количество способов прийти с позиции (i - step)
            // step <= i - проверка, чтобы не уйти в отрицательный индекс
            dp[i] += dp[i - step];
        }
    }
 
    // Возвращаем количество способов достичь ступеньки n
    return dp[n];
}
 
// Примеры использования:
climbStairs(5, 2); // Классическая задача: шаги 1,2
climbStairs(5, 4); // Расширенная версия: шаги 1,2,3,4
climbStairs(10, 3); // Шаги 1,2,3