动态规划基础#
一句话答案#
DP 四步：定义状态→写转移方程→确定初始值→确定遍历顺序，核心条件：最优子结构+重叠子问题。
核心要点
经典模型：
| 模型 | 例题 | 转移 |
|---|---|---|
| 线性DP | 最长递增子序列 | dp[i]=max(dp[j]+1) |
| 背包 | 0-1背包 | dp[i][w]=max(不选,选) |
| 区间DP | 戳气球 | dp[i][j]=max(dp[i][k]+dp[k][j]) |
空间优化： 二维→一维滚动数组
0-1 背包滚动数组为何逆序#
二维原型： dp[i][w] = max(dp[i-1][w], dp[i-1][w-c] + v)，决策「第 i 个物品选不选」只依赖上一行（i-1） 的两个值。
降一维的关键： 滚一维 dp[w] 复用上一行。问题在于把外层 i 抹掉后，dp[w] 是「正在被本轮覆盖」的数组——遍历容量 w 的方向决定 dp[w-c] 取到的是上一行还是本行。
❌ 正序遍历（w 从小到大）会出错：
- 算
dp[w]时dp[w-c]（w-c < w）本轮已经被更新过，已经是「考虑了第 i 个物品」的值 dp[w] = dp[w-c] + v相当于在「已含第 i 个物品」的基础上再加一次 → 同一物品被选了多次，退化成完全背包
✅ 逆序遍历（w 从大到小）才正确：
- 算
dp[w]时dp[w-c]（w-c < w）本轮还没被触碰，仍是上一行（只考虑前 i-1 个物品）的值 - 严格对应
dp[i-1][w-c]，保证每个物品只被选一次
一句话：逆序让
dp[w-c]保持「旧值（上一个物品的状态）」，正序则会读到「本物品刚写入的新值」从而重复选。
对比｜完全背包正是要正序：
| 遍历方向 | dp[w-c] 含义 | 物品可选次数 | |
|---|---|---|---|
| 0-1 背包 | 容量逆序 | 上一行（前 i-1 个） | 每个最多 1 次 |
| 完全背包 | 容量正序 | 本行（已含第 i 个） | 每个无限次 |
完全背包
dp[i][w]=max(dp[i-1][w], dp[i][w-c]+v)决策依赖本行 dp[i][w-c]，所以正序「读到刚更新的值」恰好就是它想要的——同一物品重复选正是目的。两者只差遍历方向一个字。
面试回答（2分钟版）
动态规划解题我遵循四步法：定义状态、写转移方程、确定初始值、确定遍历顺序。第一步是最关键的，dp[i]代表什么必须定义清楚，比如最长递增子序列中dp[i]表示以nums[i]结尾的最长递增子序列长度。第二步写转移方程描述dp[i]和之前状态的关系，比如dp[i]=max(dp[j]+1)其中j<i且nums[j]<nums[i]。第三步确定初始值也就是base case，比如dp[0]=1。第四步确定遍历顺序要保证计算dp[i]时它依赖的状态都已经算过了。能用DP的前提是两个条件：最优子结构即大问题的最优解包含子问题的最优解，重叠子问题即同一个子问题会被反复计算。和贪心的区别在于DP会回头看所有子问题取全局最优，贪心只看当前最优不回头。经典模型有线性DP、0-1背包、区间DP等。空间优化上如果dp[i]只依赖dp[i-1]可以用滚动数组把二维降到一维，但要注意遍历方向，0-1背包逆序遍历才能避免重复使用。
追问与易错
追问方向：
- “DP 和贪心的区别？”→ 贪心每步选局部最优且不回头，DP 需要考虑所有子问题的组合求全局最优；贪心需要证明贪心选择性质，DP 需要最优子结构 + 重叠子问题
- “怎么判断一个题能用 DP？”→ 看三个特征：①问最值/方案数/可行性 ②能拆分成规模更小的子问题 ③子问题有重叠（同一子问题被反复求解）；如果无重叠子问题可能是分治
- “空间优化的思路？”→ 观察状态转移方程的依赖关系：若 dp[i] 只依赖 dp[i-1]，可用滚动数组降为一维；二维 DP 若只依赖上一行可压缩为两行或一行（注意遍历方向）
- “0-1 背包一维数组为什么必须逆序遍历容量？”→ 一维 dp[w] 复用上一行；正序时 dp[w-c] 本轮已被更新（含本物品），相当于物品被重复选 → 退化成完全背包；逆序时 dp[w-c] 还是上一行的旧值（前 i-1 个物品），保证每个物品只选一次。完全背包反过来用正序，正是要重复选
易错点：
- ❌ DP 能解决所有优化问题——需要最优子结构+重叠子问题
- ❌ 二维 DP 都能优化为一维——取决于依赖关系