Что такое dynamic programming?
На этой странице
Dynamic Programming, DP, - подход для задач с повторяющимися подзадачами и оптимальной подструктурой. Идея: решить каждую подзадачу один раз и переиспользовать результат.
Вопрос
Что такое dynamic programming и как определить состояние и переходы?
Когда нужен DP?
Два признака:
- Overlapping subproblems - одни и те же подзадачи повторяются.
- Optimal substructure - ответ строится из ответов меньших подзадач.
Пример: лестница
Условие (Climbing Stairs): лестница из n ступенек, за один шаг можно подняться на 1 или на 2 ступеньки. Сколько существует разных способов дойти до верха?
Для n = 4 способов 5:
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2Перебирать все варианты долго - их число растет экспоненциально. Заметим главное: на ступеньку i можно попасть только с i - 1 (шагом 1) или с i - 2 (шагом 2). Значит:
ways(i) = ways(i - 1) + ways(i - 2)Это и есть DP: ответ для большой задачи складывается из ответов для меньших.
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| ways(i) | 1 | 2 | 1 + 2 = 3 | 2 + 3 = 5 | 3 + 5 = 8 |
Как решать DP-задачу по шагам
- State - что означает одна ячейка:
dp[i]- число способов дойти до ступенькиi. - Transition - как ячейка считается через предыдущие:
dp[i] = dp[i - 1] + dp[i - 2]. - Base cases - что известно без вычислений:
dp[1] = 1,dp[2] = 2. - Порядок - от маленьких
iк большим, чтобы нужные ячейки уже были посчитаны. - Answer - где лежит итог:
dp[n].
Top-down
Memoization:
function climbStairs(n: number, memo = new Map<number, number>()): number {
if (n <= 2) return n
if (memo.has(n)) return memo.get(n)!
const ways = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
memo.set(n, ways)
return ways
}Bottom-up
Tabulation:
function climbStairs(n: number): number {
if (n <= 2) return n
const dp = new Array(n + 1).fill(0)
dp[1] = 1
dp[2] = 2
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}Top-down и bottom-up дают одинаковый ответ и одинаковую сложность O(n). Top-down проще написать из рекурсивного решения, bottom-up не использует call stack.
Space optimization
dp[i] зависит только от двух предыдущих значений, поэтому весь массив хранить не нужно:
function climbStairs(n: number): number {
if (n <= 2) return n
let prev2 = 1
let prev1 = 2
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2
prev2 = prev1
prev1 = current
}
return prev1
}Что отвечать на собеседовании?
DP применяют, когда задача состоит из повторяющихся подзадач, а ответ можно построить из меньших ответов. Есть top-down подход с memoization и bottom-up подход с таблицей. Сложность обычно считается как количество states умножить на стоимость transition.
Что важно помнить: частые ошибки
- Применять DP там, где нет повторных подзадач.
- Не определить state.
- Не определить transition.
- Не задать base cases.
- Забыть порядок заполнения bottom-up.
Мини-шпаргалка
- State - что храним.
- Transition - как считаем.
- Base cases - старт.
- Answer - где лежит итог.
- Top-down = memo.
- Bottom-up = table.