Лестница (подъём по ступенькам)

Подъём по лестнице (Climbing Stairs)

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

1. Анализ проблемы

Ключевое наблюдение: чтобы достичь ступеньки n, мы можем:

• Подняться на 1 ступеньку из позиции (n-1)
• Подняться на 2 ступеньки из позиции (n-2)

Поэтому:

f(n) = f(n-1) + f(n-2)

Это рекуррентное соотношение Фибоначчи!

Примеры:

f(1) = 1        (способ: [1])
f(2) = 2        (способы: [1+1], [2])
f(3) = 3        (способы: [1+1+1], [1+2], [2+1])
f(4) = 5        (способы: [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2])
f(5) = 8        (f(4) + f(3) = 5 + 3 = 8)

2. Решение 1: Наивная рекурсия (неоптимально)

def climb_stairs_recursive(n: int) -> int:
    """Простая рекурсия без мемоизации."""
    
    # Базовые случаи
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # Рекурсивное соотношение
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# Тестирование
print(climb_stairs_recursive(3))   # 3
print(climb_stairs_recursive(5))   # 8

Анализ сложности:

• Время: O(2^n) — экспоненциальная, ОЧЕНЬ медленно
• Память: O(n) — стек рекурсии

Почему так медленно?

Вычисление f(5):
              f(5)
            /      \
          f(4)      f(3)
         /    \      /    \
       f(3)   f(2) f(2)  f(1)
      / \     
    f(2) f(1)
    / \
  f(1) f(0)

Видно, что f(3), f(2) вычисляются МНОГОКРАТНО!

3. Решение 2: Рекурсия с мемоизацией (хорошо)

def climb_stairs_memo(n: int, memo: dict = None) -> int:
    """Рекурсия с кэшированием результатов."""
    
    if memo is None:
        memo = {}
    
    # Базовые случаи
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # Проверяем, вычисляли ли уже
    if n in memo:
        return memo[n]
    
    # Вычисляем и сохраняем
    memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
    return memo[n]

# Использование
print(climb_stairs_memo(5))  # 8
print(climb_stairs_memo(50)) # Работает быстро!

Анализ сложности:

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

С использованием декоратора:

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs_cached(n: int) -> int:
    """Рекурсия с встроенным кэшем."""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_cached(n - 1) + climb_stairs_cached(n - 2)

4. Решение 3: Динамическое программирование — Bottom-Up (оптимально)

def climb_stairs_dp(n: int) -> int:
    """DP решение с таблицей."""
    
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # Создаём таблицу
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    # Заполняем таблицу снизу вверх
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# Тестирование
print(climb_stairs_dp(3))   # 3
print(climb_stairs_dp(5))   # 8
print(climb_stairs_dp(100)) # Мгновенно!

Визуализация:

Таблица для n=5:
Индекс: 0  1  2  3  4  5
Значение: 0  1  2  3  5  8
              ↑  ↑  ↑  ↑  ↑
         base dp[1]+dp[0] → 1
              dp[2]+dp[1] → 3
              dp[3]+dp[2] → 5
              dp[4]+dp[3] → 8

Анализ сложности:

• Время: O(n) — один цикл
• Память: O(n) — массив DP

5. Решение 4: Оптимизированная память (лучшее)

Поскольку dp[i] зависит только от двух предыдущих значений, можно использовать две переменные вместо массива:

def climb_stairs_optimized(n: int) -> int:
    """DP с оптимизацией памяти O(1)."""
    
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # Используем две переменные вместо массива
    prev2 = 1  # f(1)
    prev1 = 2  # f(2)
    
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

# Тестирование
print(climb_stairs_optimized(5))   # 8
print(climb_stairs_optimized(100)) # Быстро и экономно!

Анализ сложности:

• Время: O(n)
• Память: O(1) — только две переменные

6. Решение 5: Матричное возведение в степень (Hardcore)

def climb_stairs_matrix(n: int) -> int:
    """Решение через матрицы (O(log n))."""
    
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    def matrix_multiply(a, b):
        """Умножение 2x2 матриц."""
        return [
            [a[0][0] * b[0][0] + a[0][1] * b[1][0],
             a[0][0] * b[0][1] + a[0][1] * b[1][1]],
            [a[1][0] * b[0][0] + a[1][1] * b[1][0],
             a[1][0] * b[0][1] + a[1][1] * b[1][1]]
        ]
    
    def matrix_power(matrix, exp):
        """Возведение матрицы в степень."""
        if exp == 1:
            return matrix
        
        if exp % 2 == 0:
            half = matrix_power(matrix, exp // 2)
            return matrix_multiply(half, half)
        else:
            return matrix_multiply(matrix, matrix_power(matrix, exp - 1))
    
    # Матрица трансформации Фибоначчи
    base_matrix = [[1, 1], [1, 0]]
    result = matrix_power(base_matrix, n - 1)
    
    # f(n) = 2*f(n-1) + f(n-2) → берём элемент [0][0]
    return result[0][0] + result[0][1]

# Для очень больших n (например, 10^18)
# Это даёт O(log n) вместо O(n)!

7. Полный набор тестов

import unittest

class TestClimbStairs(unittest.TestCase):
    
    def setUp(self):
        self.climb = climb_stairs_optimized  # Тестируем оптимальное решение
    
    def test_base_cases(self):
        self.assertEqual(self.climb(0), 0)
        self.assertEqual(self.climb(1), 1)
        self.assertEqual(self.climb(2), 2)
    
    def test_small_values(self):
        self.assertEqual(self.climb(3), 3)  # [1+1+1, 1+2, 2+1]
        self.assertEqual(self.climb(4), 5)  # [1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2]
        self.assertEqual(self.climb(5), 8)
    
    def test_large_values(self):
        # Проверяем, что работает без переполнения
        result = self.climb(50)
        self.assertGreater(result, 0)
        self.assertEqual(result, 20365011074)  # Известное значение
    
    def test_fibonacci_pattern(self):
        # Проверяем, что это действительно Фибоначчи
        results = [self.climb(i) for i in range(1, 8)]
        expected = [1, 2, 3, 5, 8, 13, 21]
        self.assertEqual(results, expected)

if __name__ == '__main__':
    unittest.main()

8. Сравнение всех подходов

9. Измерение производительности

import time

def benchmark(func, n):
    start = time.perf_counter()
    result = func(n)
    end = time.perf_counter()
    return result, (end - start) * 1000  # в миллисекундах

n = 1000

result, time_dp = benchmark(climb_stairs_optimized, n)
print(f"DP решение: {result}, время: {time_dp:.3f}ms")

# Результат:
# DP решение: 70330185894131, время: 0.012ms

# Наивная рекурсия для n=40 уже занимает несколько секунд!

10. Обобщение: подъём с шагами k размеров

def climb_stairs_k_steps(n: int, k: int) -> int:
    """Можно подниматься на 1, 2, ..., k ступенек за раз."""
    
    if n <= 0:
        return 0
    
    dp = [0] * (n + 1)
    dp[0] = 1  # Один способ остаться на месте
    
    for i in range(1, n + 1):
        for j in range(1, min(k, i) + 1):
            dp[i] += dp[i - j]
    
    return dp[n]

# Примеры:
print(climb_stairs_k_steps(5, 2))  # 8 (как обычная лестница)
print(climb_stairs_k_steps(5, 3))  # 13 (можно делать шаги 1, 2 или 3)

Вывод

Для задачи "Climbing Stairs":

1. Лучшее решение: Оптимизированное DP с O(n) временем и O(1) памятью
2. Рекуррентное соотношение: f(n) = f(n-1) + f(n-2) (Фибоначчи)
3. Граничные случаи: n=0 → 0, n=1 → 1, n=2 → 2
4. На интервью: Сначала покажи наивное решение, потом оптимизируй
5. Вариации: Можно обобщить на k размеров шагов

Это одна из самых частых задач на собеседованиях — хорошо её понимайте!