Решение задачи "Climbing Stairs": пошаговый разбор всех подходов

Почему задача "Climbing Stairs" важна?

Задача "Climbing Stairs" (Подъем по лестнице) — это классическая алгоритмическая задача, которая является отличным введением в мир динамического программирования. Она позволяет оценить:

• 🧠 Умение распознавать задачи с оптимальной подструктурой
• ⚡ Навыки применения рекурсии и понимание её ограничений
• 🎯 Способность оптимизировать решения с помощью мемоизации
• 🔍 Умение находить математические закономерности в алгоритмических задачах
• 💼 Практические навыки решения задач, часто встречающихся на технических собеседованиях

Постановка задачи

Формулировка с LeetCode:

Вы поднимаетесь по лестнице. Требуется n шагов, чтобы достичь вершины.

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

Математическая формулировка:

Найти количество способов F(n), которыми можно подняться на n-ую ступеньку, если за один ход можно подняться на 1 или 2 ступеньки.

Примеры:

// Пример 1 ✅
Input: n = 2
Output: 2
Объяснение: Существует два способа подняться на вершину.
1. 1 шаг + 1 шаг
2. 2 шага

// Пример 2 ✅
Input: n = 3
Output: 3
Объяснение: Существует три способа подняться на вершину.
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Понимание задачи

Прежде чем перейти к решениям, давайте глубже поймем задачу. Рассмотрим ещё несколько примеров:

• Для n = 1: Только 1 способ (1 шаг)
• Для n = 2: 2 способа (1+1 или 2)
• Для n = 3: 3 способа (1+1+1, 1+2, 2+1)
• Для n = 4: 5 способов (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
• Для n = 5: 8 способов

Видите закономерность? Количество способов для n образует последовательность Фибоначчи (начиная с F(1) = 1, F(2) = 2).

Это происходит потому, что для того, чтобы подняться на n-ую ступеньку, мы можем:

1. Подняться на (n-1)-ую ступеньку и затем сделать 1 шаг
2. Подняться на (n-2)-ую ступеньку и затем сделать 2 шага

Таким образом, F(n) = F(n-1) + F(n-2).

Подходы к решению

Решение 1: Рекурсивный подход (без оптимизации) 🔍

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  // Базовые случаи
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  
  // Рекурсивный случай
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Анализ решения:

✅ Простая и интуитивная реализация

✅ Прямо отражает математическое определение

❌ Экспоненциальная временная сложность O(2^n)

❌ Многократный пересчет одних и тех же значений

❌ Приводит к переполнению стека для больших n

Решение 2: Рекурсия с мемоизацией (нисходящее ДП) 🚀

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  // Создаем массив для хранения уже вычисленных значений
  const memo = new Array(n + 1).fill(-1);
  
  // Вспомогательная функция с мемоизацией
  function climb(i) {
    // Базовые случаи
    if (i === 1) {
      return 1;
    }
    if (i === 2) {
      return 2;
    }
    
    // Проверяем, вычисляли ли мы уже это значение
    if (memo[i] !== -1) {
      return memo[i];
    }
    
    // Вычисляем и сохраняем результат
    memo[i] = climb(i - 1) + climb(i - 2);
    return memo[i];
  }
  
  return climb(n);
}

Характеристики:

✅ Значительное улучшение производительности по сравнению с простой рекурсией

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

✅ Пространственная сложность O(n) для хранения мемоизированных значений

❌ Всё ещё использует стек рекурсии, что может вызвать проблемы для очень больших n

Решение 3: Динамическое программирование (восходящий подход) 📈

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  // Обрабатываем базовые случаи
  if (n === 1) {
    return 1;
  }
  
  // Создаем массив для хранения промежуточных результатов
  const dp = new Array(n + 1);
  
  // Инициализируем базовые случаи
  dp[1] = 1; // Один способ подняться на 1-ую ступеньку
  dp[2] = 2; // Два способа подняться на 2-ую ступеньку
  
  // Заполняем массив dp
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

Преимущества и недостатки:

✅ Устраняет проблемы с переполнением стека рекурсии

✅ Временная сложность O(n) - линейное время выполнения

✅ Ясный и читабельный код

❌ Требует O(n) дополнительной памяти для хранения массива dp

Решение 4: Оптимизированное ДП с константной памятью 🔧

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  // Обрабатываем базовые случаи
  if (n === 1) {
    return 1;
  }
  
  // Инициализируем первые два значения
  let first = 1; // F(1)
  let second = 2; // F(2)
  
  // Вычисляем значения от F(3) до F(n)
  for (let i = 3; i <= n; i++) {
    const current = first + second;
    first = second;
    second = current;
  }
  
  return second;
}

Особенности:

✅ Оптимальная временная сложность O(n)

✅ Пространственная сложность O(1) - требуется только константное количество памяти

✅ Быстрое и эффективное решение

✅ Подходит для очень больших значений n (с учетом ограничений языка)

Решение 5: Математический подход с использованием формулы Бине 🧮

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  // Формула Бине для n-го числа Фибоначчи (адаптированная для нашей задачи)
  const sqrt5 = Math.sqrt(5);
  const fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
  return Math.round(fibn / sqrt5);
}

Преимущества и недостатки:

✅ Временная сложность O(1) - константное время выполнения

✅ Пространственная сложность O(1) - требуется константное количество памяти

❌ Может привести к ошибкам округления для больших n

❌ Менее интуитивное решение с точки зрения понимания алгоритма

Сравнение подходов

Визуализация динамического программирования

Рассмотрим решение задачи для n = 5 с использованием DP:

dp[1] = 1 (базовый случай)
dp[2] = 2 (базовый случай)
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

Результат: 8 различных способов подняться на 5-ю ступеньку.

Оптимизации и расширения

Подход для больших чисел

Для очень больших n можно использовать быстрое возведение в степень для вычисления чисел Фибоначчи:

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  // Матричное возведение в степень для чисел Фибоначчи
  function multiplyMatrix(A, B) {
    const C = Array(2).fill().map(() => Array(2).fill(0));
    
    for (let i = 0; i < 2; i++) {
      for (let j = 0; j < 2; j++) {
        for (let k = 0; k < 2; k++) {
          C[i][j] += A[i][k] * B[k][j];
        }
      }
    }
    
    return C;
  }
  
  function matrixPower(A, n) {
    if (n === 1) {
      return A;
    }
    
    if (n % 2 === 0) {
      const halfPower = matrixPower(A, n / 2);
      return multiplyMatrix(halfPower, halfPower);
    } else {
      const halfPower = matrixPower(A, (n - 1) / 2);
      const squareHalfPower = multiplyMatrix(halfPower, halfPower);
      return multiplyMatrix(A, squareHalfPower);
    }
  }
  
  // Базовые случаи
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  const baseMatrix = [
    [1, 1],
    [1, 0]
  ];
  
  // Для Fib(n+1), нам нужно возвести матрицу в степень n
  const resultMatrix = matrixPower(baseMatrix, n);
  
  // F(n+1) находится в ячейке [0][0]
  return resultMatrix[0][0];
}

Расширение задачи: разные размеры шагов

Можно расширить задачу, позволяя делать шаги разной длины:

/**
 * @param {number} n - количество ступенек
 * @param {number[]} steps - возможные размеры шагов
 * @return {number}
 */
function climbStairsWithSteps(n, steps) {
  // Создаем массив dp
  const dp = new Array(n + 1).fill(0);
  
  // Базовый случай: один способ не подниматься
  dp[0] = 1;
  
  // Заполняем массив dp
  for (let i = 1; i <= n; i++) {
    for (const step of steps) {
      if (i - step >= 0) {
        dp[i] += dp[i - step];
      }
    }
  }
  
  return dp[n];
}

// Пример использования
console.log(climbStairsWithSteps(5, [1, 2])); // 8
console.log(climbStairsWithSteps(5, [1, 2, 3])); // 13

Распространенные ошибки

1. 🤦‍♂️ Неправильные базовые случаи: Забывание особых случаев для n = 1 или n = 2
2. 😅 Путаница с индексацией: Использование неправильных индексов при работе с массивом dp
3. 🐛 Игнорирование переполнения стека: Попытка решить задачу простой рекурсией для больших n
4. 😕 Ошибки при оптимизации памяти: Неправильная замена переменных в оптимизированном ДП

Интервью: что следует помнить

При решении этой задачи на техническом интервью важно:

1. Распознать закономерность Фибоначчи

   Сразу укажите интервьюеру, что вы заметили: количество способов подняться на n-ую ступеньку равно сумме способов подняться на (n-1)-ую и (n-2)-ую ступеньки. Это характерный признак последовательности Фибоначчи (с небольшим сдвигом).

2. Обсудить несколько подходов

   Продемонстрируйте глубину понимания, упомянув разные подходы: рекурсия, мемоизация, ДП, оптимизированное ДП и математические формулы.

3. Проанализировать сложность

   Обязательно проанализируйте временную и пространственную сложность каждого рассматриваемого решения.

4. Оптимизировать в правильном направлении

   Начните с интуитивного решения и постепенно улучшайте его, демонстрируя способность оптимизировать код.

5. Проверить граничные случаи

   Не забудьте о базовых случаях (n = 1, n = 2) и обсудите потенциальные проблемы для очень больших n.

Заключение

Задача "Climbing Stairs" — это классический пример того, как динамическое программирование позволяет оптимизировать рекурсивные решения. Она демонстрирует важный принцип: если задача имеет оптимальную подструктуру (оптимальное решение может быть построено из оптимальных решений подзадач), то, скорее всего, она может быть эффективно решена с помощью ДП.

Ключевые выводы:

• 🤹‍♂️ Распознавание закономерностей (в данном случае, последовательности Фибоначчи) может значительно упростить решение
• 📊 Динамическое программирование превращает экспоненциальное решение в линейное
• 🧠 Мемоизация — это простой способ оптимизировать рекурсивные решения
• 🔄 Оптимизация пространственной сложности часто возможна при итеративном подходе
• 💡 Для некоторых задач существуют математические формулы, дающие мгновенный результат

Эта задача является отличным введением в мир динамического программирования и часто встречается на технических собеседованиях именно потому, что позволяет продемонстрировать понимание различных алгоритмических подходов и умение оптимизировать решения. 🌟