参考：DP 基础 API、模型与设计速查
基于通用算法概念 · 核于 2026-07
速查
- DP 三要素：①状态定义（
dp[...]代表什么）；②状态转移方程（从「最后一步」倒推）；③边界条件（最小初始值）。 - 两个核心特征：最优子结构（子问题最优能推出全局最优）+ 重叠子问题（子问题反复出现，需记忆化）。
- 两种实现：自顶向下记忆化递归（贴近直觉、只算用到的子问题）；自底向上递推填表（常数小、易空间优化）。
- 斐波那契：
dp[i]=dp[i-1]+dp[i-2]，边界dp[1]=dp[2]=1，O(n) 时间 O(1) 空间。 - 爬楼梯：
dp[i]=dp[i-1]+dp[i-2]，边界dp[1]=1, dp[2]=2，O(n) 时间 O(1) 空间。 - 打家劫舍：
dp[i]=max(dp[i-1], dp[i-2]+nums[i])，O(n) 时间 O(1) 空间。 - Kadane：
dp[i]=max(nums[i], dp[i-1]+nums[i])，答案取max(dp[i])，O(n) 时间 O(1) 空间。 - 0-1 背包：
dp[j]=max(dp[j], dp[j-w]+v)，容量倒序，O(n·W) 时间 O(W) 空间。 - 完全背包：
dp[j]=max(dp[j], dp[j-w]+v)，容量正序，O(n·W) 时间 O(W) 空间。 - 零钱兑换 II（组合数）：
dp[j]+=dp[j-coin]，外层物品内层容量正序，dp[0]=1。 - 零钱兑换 I（最少硬币）：
dp[j]=min(dp[j], dp[j-coin]+1)，dp[0]=0其余Infinity。 - 组合 vs 排列：外层物品内层容量 → 组合；外层容量内层物品 → 排列。
- 交互演示：0-1 背包、完全背包、零钱兑换。
一、DP 三要素与两个前提
| 要素 | 含义 | 示例（爬楼梯） |
|---|---|---|
| 状态定义 | dp[...] 代表什么 | dp[i] = 爬到第 i 阶的方案数 |
| 转移方程 | dp[i] 怎么由更小子问题推出 | dp[i] = dp[i-1] + dp[i-2] |
| 边界条件 | 不依赖转移的初始值 | dp[1]=1, dp[2]=2 |
两个隐性前提：最优子结构（大问题最优解 = 子问题最优解的组合）+ 无后效性（未来只依赖当前状态，不依赖到达路径）。
二、常见基础模型表
| 模型 | 状态定义 | 转移方程 | 边界 | 时间 | 空间 |
|---|---|---|---|---|---|
| 斐波那契 | dp[i]=第 i 个斐波那契数 | dp[i]=dp[i-1]+dp[i-2] | dp[1]=dp[2]=1 | O(n) | O(1) |
| 爬楼梯 | dp[i]=到 i 阶方案数 | dp[i]=dp[i-1]+dp[i-2] | dp[1]=1, dp[2]=2 | O(n) | O(1) |
| 打家劫舍 | dp[i]=前 i 家最大金额 | dp[i]=max(dp[i-1], dp[i-2]+nums[i]) | dp[0]=0, dp[1]=nums[0] | O(n) | O(1) |
| Kadane | dp[i]=以 i 结尾最大和 | dp[i]=max(nums[i], dp[i-1]+nums[i]) | dp[0]=nums[0] | O(n) | O(1) |
| 0-1 背包 | dp[j]=容量 j 最大价值 | dp[j]=max(dp[j], dp[j-w]+v) | dp[0..W]=0 | O(n·W) | O(W) |
| 完全背包 | dp[j]=容量 j 最大价值 | dp[j]=max(dp[j], dp[j-w]+v) | dp[0..W]=0 | O(n·W) | O(W) |
| 零钱兑换 II | dp[j]=凑 j 元组合数 | dp[j]+=dp[j-coin] | dp[0]=1 | O(n·W) | O(W) |
| 零钱兑换 I | dp[j]=凑 j 元最少硬币 | dp[j]=min(dp[j], dp[j-coin]+1) | dp[0]=0, 其余 ∞ | O(n·W) | O(W) |
三、背包代码模板
0-1 背包（一维倒序）
js
// 每件最多放一次，求最大价值
function knapsack01(w, v, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < w.length; i++) {
for (let j = W; j >= w[i]; j--) { // 倒序——灵魂
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[W];
}完全背包（一维正序）
js
// 每件无限件，求最大价值
function knapsackComplete(w, v, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < w.length; i++) {
for (let j = w[i]; j <= W; j++) { // 正序——灵魂
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[W];
}零钱兑换 II（组合数）
js
// 凑 amount 元的组合数（外层物品内层容量=组合）
function change(amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let j = coin; j <= amount; j++) dp[j] += dp[j - coin];
}
return dp[amount];
}四、DP 设计五步
- 定义状态：
dp[...]代表什么（满足无后效性，包含所有影响未来的信息）。 - 找转移方程：从「最后一步」倒推，枚举所有可能的最后一步取最优。
- 定边界条件：最小的初始值（
dp[0]、dp[1]等）。 - 确定计算顺序：保证算
dp[i]时依赖项已就绪（一维从小到大；背包外层物品内层容量）。 - 优化空间：滚动数组 / 一维化（0-1 背包倒序、完全背包正序）。
五、记忆化 vs 递推速查
| 维度 | 记忆化递归（自顶向下） | 递推填表（自底向上） |
|---|---|---|
| 方向 | 大问题 → 边界 | 边界 → 大问题 |
| 形态 | 递归 + memo | for 循环 + dp 数组 |
| 子问题 | 只算用到的 | 全部算一遍 |
| 栈 / 常数 | 有递归栈，可能溢出 | 无栈，常数小 |
| 空间优化 | 难 | 易（滚动 / 一维化） |
| 选型 | 状态稀疏、思路梳理 | 要常数优势、要空间优化 |
六、易错点清单
- 状态定义错：状态没包含所有影响未来的信息 → 后效性破坏 → 转移不正确（需扩展状态维度）。
- 边界漏写 / 写错：
dp[0]、dp[1]必须显式给出；组合数问题dp[0]=1（「什么都不选」算 1 种），漏了全 0。 - 0-1 背包忘倒序：一维化后容量正序遍历会退化成完全背包（一件物品被放多次）——最高频坑。
- 完全背包忘正序：误用倒序会导致「每件只用一次」，丢失无限件的语义。
- 组合 vs 排列搞反：求组合数（不区分顺序）必须外层物品内层容量；求排列数（区分顺序）反过来。零钱兑换 II 用前者，爬楼梯用后者。
- Kadane 答案取错：状态是「以 i 结尾」，答案是
max(dp[i])不是dp[n-1]。 - 初始化值用错：求最大值初始化
0或-∞（看是否允许空）；求最小值初始化Infinity，dp[0]=0。 - 递推顺序错：区间 DP 要先短后长；背包要外层物品内层容量——顺序反了依赖项未就绪。
- 记忆化忘判「已算过」：递归入口先查 memo，没有才计算并存——否则等于没记忆化。
- 空间优化后引用旧值：滚动数组若用「覆盖」而非「双缓冲」，要确认覆盖顺序不破坏后续依赖（0-1 背包倒序正是为此）。
- 混淆 dp 维度下标：物品下标 i 常与 dp 行号 i 差 1（
dp[i]对应物品w[i-1]），off-by-one 高频。
七、如何识别 DP 题
- 问最值：「最大/最小/最长/最短/最少」。
- 问方案数 / 可行性：「有多少种」「能否凑成/组成」。
- 结构信号：连续子数组、子序列、子集、划分、凑金额。
- 能拆成语义相同的子问题且子问题重叠。
- 三者满足 → 按「定义状态 → 找转移 → 定边界 → 定顺序 → 优化空间」五步走。
八、进阶方向（链接其他叶）
- 序列区间 DP：最长公共子序列（LCS）、最长递增子序列（LIS）、编辑距离 —— DP 三部曲之二
- 进阶 DP：树形 DP、数位 DP、状压 DP、换根 DP —— DP 三部曲之三
- 回溯 / 记忆化搜索：DP 的递归视角，状态空间大时优先 —— 见回溯叶
- 贪心：能严格证明局部最优 ⇒ 全局最优时优先 —— 见贪心叶