Dynamic Programming (Динамическое программирование)
Когда применять:
- Optimization: Найти min/max путь, стоимость, количество.
- Overlapping Subproblems: Задача разбивается на подзадачи, которые повторяются (Fibonacci).
- Optimal Substructure: Оптимальное решение подзадачи ведет к оптимальному решению всей задачи.
1D DP (Одномерная динамика)
Пример: Climbing Stairs (Сколько способов подняться на N ступенек, 1 или 2 шага).
dp[i] = dp[i-1] + dp[i-2]
// Space Optimized O(1)
let prev1 = 1, prev2 = 1; // base cases for 0 and 1
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;2D DP (Двумерная динамика / Grid)
Пример: Unique Paths (Сколько путей из (0,0) в (m,n)).
dp[i][j] = dp[i-1][j] (сверху) + dp[i][j-1] (слева)
const dp = Array(m).fill().map(() => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];