Dynamic Programming: Основы

Динамическое программирование — решение сложных задач через комбинацию решений перекрывающихся подзадач. Мемоизация (top-down) и табуляция (bottom-up).

#1. Суть паттерна

DP применяется, когда задача имеет:

Перекрывающиеся подзадачи — одни и те же подзадачи решаются многократно
Оптимальную подструктуру — оптимальное решение строится из оптимальных решений подзадач

#Подходы

Подход	Описание	Когда использовать
Мемоизация (Top-Down)	Рекурсия + кэш	Проще в реализации
Табуляция (Bottom-Up)	Итерация + таблица	Лучше производительность

#2. Climbing Stairs (LeetCode 70) 🟩 Easy

Ссылка: https://leetcode.com/problems/climbing-stairs/

Условие: Вы поднимаетесь на лестницу. Нужно n шагов, чтобы достичь вершины. Каждый раз вы можете подняться на 1 или 2 ступеньки.

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

Примеры:

Ввод: n = 2
Вывод: 2
Объяснение: 1+1, 2

Ввод: n = 3
Вывод: 3
Объяснение: 1+1+1, 1+2, 2+1

Решение:

# Мемоизация (Top-Down)
def climbStairs(n):
    memo = {}

    def dp(i):
        if i <= 2:
            return i
        if i not in memo:
            memo[i] = dp(i-1) + dp(i-2)
        return memo[i]

    return dp(n)

# Табуляция (Bottom-Up) с оптимизацией
def climbStairs(n):
    if n <= 2:
        return n

    prev1, prev2 = 2, 1
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

Объяснение:

dp[i] = dp[i-1] + dp[i-2] — числа Фибоначчи
Базовые случаи: dp[1] = 1, dp[2] = 2
Оптимизация: храните только последние два значения

Сложность:

Время: O(n)
Память: O(1) с оптимизацией

#3. Min Cost Climbing Stairs (LeetCode 746) 🟩 Easy

Ссылка: https://leetcode.com/problems/min-cost-climbing-stairs/

Условие: Дан массив cost, где cost[i] — стоимость i-й ступеньки. Вы можете начать с ступеньки 0 или 1 и подниматься на 1 или 2 ступеньки за раз.

Верните минимальную стоимость достижения вершины (за пределами последней ступеньки).

Примеры:

Ввод: cost = [10,15,20]
Вывод: 15

Ввод: cost = [1,100,1,1,1,100,1,1,100,1]
Вывод: 6

Решение:

def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)

    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

    return dp[n]

Объяснение:

dp[i] — минимальная стоимость достижения ступеньки i
dp[0] = dp[1] = 0 (можно начать с любой из них)
Ответ: dp[n] — стоимость достижения вершины

Сложность: O(n)

#4. Шпаргалка

Задача	Формула
Climbing Stairs	dp[i] = dp[i-1] + dp[i-2]
Min Cost Climbing	dp[i] = min(dp[i-1]+cost, dp[i-2]+cost)

#5. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильные базовые случаи

# ❌ Неправильно для Climbing Stairs
dp[0] = 0, dp[1] = 0  # dp[1] должно быть 1!

# ✅ Правильно
dp[1] = 1, dp[2] = 2

#❌ Ошибка 2: Неправильный индекс для cost

# ❌ Неправильно
dp[i] = min(dp[i-1] + cost[i], dp[i-2] + cost[i])

# ✅ Правильно
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

#6. Заключение

Dynamic Programming: Основы — базовые задачи на лестницы.

Ключевые принципы:

Climbing Stairs: числа Фибоначчи
Min Cost: min из двух предыдущих + cost
Оптимизация памяти: хранить только последние 2 значения

Подход

Описание

Когда использовать

Мемоизация (Top-Down)

Рекурсия + кэш

Проще в реализации

Табуляция (Bottom-Up)

Итерация + таблица

Лучше производительность

Задача

Формула

Climbing Stairs

dp[i] = dp[i-1] + dp[i-2]

Min Cost Climbing

dp[i] = min(dp[i-1]+cost, dp[i-2]+cost)

DP: Основы