Climbing Stairs, Min Cost Climbing Stairs.
Динамическое программирование — решение сложных задач через комбинацию решений перекрывающихся подзадач. Мемоизация (top-down) и табуляция (bottom-up).
DP применяется, когда задача имеет:
| Подход | Описание | Когда использовать |
|---|---|---|
| Мемоизация (Top-Down) | Рекурсия + кэш | Проще в реализации |
| Табуляция (Bottom-Up) | Итерация + таблица | Лучше производительность |
Условие:
Вы поднимаетесь на лестницу. Нужно 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Объяснение:
Сложность:
Условие:
Дан массив 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]Объяснение:
Сложность: O(n)
| Задача | Формула |
|---|---|
| Climbing Stairs | dp[i] = dp[i-1] + dp[i-2] |
| Min Cost Climbing | dp[i] = min(dp[i-1]+cost, dp[i-2]+cost) |
# ❌ Неправильно для Climbing Stairs
dp[0] = 0, dp[1] = 0 # dp[1] должно быть 1!
# ✅ Правильно
dp[1] = 1, dp[2] = 2# ❌ Неправильно
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])Dynamic Programming: Основы — базовые задачи на лестницы.
Ключевые принципы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.