Skip to main content

动态规划入门专题

DP 的核心是「状态定义」。定义对了，转移方程往往就出来了；定义错了，怎么写都别扭。很多人背了一堆模型还是不会做新题，根因是没在「状态定义」上花时间。

一、状态、转移、边界​

状态定义是最关键的一步，也是最容易错的一步。写完状态后问自己两个问题：这个状态能不能唯一描述当前局面？答案能不能从它直接读出？然后是转移方程（当前状态由哪些更小的状态推出来）与边界与遍历顺序（填表时依赖的状态必须先算好）。

自顶向下的可靠路径是：先写暴力递归，确认能跑通，再加记忆化。这比一开始就硬想状态数组直观得多——递归就是「用自然语言描述子问题」，记忆化只是把重复子问题缓存起来。

// 自顶向下：先写递归，再加 memo（爬楼梯类）
function climb(n, memo = new Map()) {
  if (n <= 1) return 1
  if (memo.has(n)) return memo.get(n)
  const r = climb(n - 1, memo) + climb(n - 2, memo)
  memo.set(n, r)
  return r
}
// 自底向上：填表，从最小子问题往上算
function climbDP(n) {
  const dp = [1, 1]
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]
  return dp[n]
}

状态定义错了，转移方程怎么推都别扭

二、自顶向下与自底向上​

自顶向下（递归 + memo）好写，顺着思维来，但要注意递归深度（链特别长会爆栈）。自底向上（填表）好优化，遍历顺序可控，空间压缩更容易做。两者在「算出了什么」上完全等价，区别在实现与边界处理。

填表最怕的是遍历顺序错——某个状态依赖的状态还没算就被读了，结果全是 undefined。写之前先列清楚「dp[i] 依赖 dp[i-?] 还是 dp[?][i-1]」，再决定外层内层怎么排。

三、几类常见模型​

认模型比背代码重要。三个常见模型：

  • 线性 DP（爬楼梯、打家劫舍）：状态是「前 i 个」的某种最值，dp[i] 由 dp[i-1] / dp[i-2] 推。
  • 背包（0-1 / 完全 / 多重）：状态是「前 i 个物品、容量 j 下的最大价值」，区别在遍历方向（0-1 倒序、完全正序）。
  • 区间 DP（最长回文子串、戳气球）：状态是「区间 [i,j] 上的结果」，按区间长度从小到大枚举。区间 DP 的套路是外层枚举区间长度 len、内层枚举起点 i、终点 j = i+len-1，保证算 [i,j] 时更短的子区间都已就绪。它常用于「在序列上做某种最优合并」类问题。

每个模型先想清楚「状态是什么、转移是什么」，再套实现。

物品j=0j=1j=2j=3j=4j=5i=0000000i=10maxmaxmaxmaxmaxi=20maxmaxmaxmaxmaxi=30maxmaxmaxmaxmaxdp[i][j] = max( dp[i-1][j], dp[i-1][j-w] + v)先想清楚「状态是什么」，再套转移：这一格要么不选第 i 件，要么选了它并从更小的容量转移过来。
图：0-1 背包的二维填表——每一格只依赖上一行的两格，这才是能压成一维的前提

每类模型的复杂度要记清楚：线性 DP 是 O(n)，01 背包是 O(n·C)（C 为容量），区间 DP 是 O(n³)（枚举长度、枚举起点，再加一层转移）。动手前先估量级——n = 10⁵ 时 O(n²) 就已经到顶了。

四、滚动数组​

滚动数组把二维压成一维，前提是当前层只依赖前一层或前几层。代价要说清楚：压缩后无法还原路径，需要输出具体方案时不能压。另外压缩会改变遍历方向——01 背包要倒序遍历，否则同一物品会被重复取用（变成完全背包），这是很多人改完就出错的地方。

// 01 背包：倒序遍历，避免同一物品被重复取用
for (const item of items) {
  for (let j = capacity; j >= item.weight; j--) {
    dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value)
  }
}

要输出方案时，额外用一个 choice 数组记录每一步选了什么，从终点回溯到起点：

// 路径还原：记录选择，从终点反向追溯
const choices = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(false))
// ... 转移时同步记录 choices[i][j] = true/false
let i = n, j = capacity, picked = []
while (i > 0) {
  if (choices[i][j]) { picked.push(i); j -= items[i].weight }
  i--
}

要输出具体方案就不能压维度，压缩前先确认不需要还原路径

// 0-1 背包：二维压一维，内层必须倒序遍历
function knapsack(weights, values, cap) {
  const dp = new Array(cap + 1).fill(0)
  for (let i = 0; i < weights.length; i++) {
    for (let c = cap; c >= weights[i]; c--) { // 倒序：保证每件物品只取一次
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i])
    }
  }
  return dp[cap]
}

倒序这一下是压缩的代价：正序会变成完全背包（每件可取多次）。想不通这一点，压缩后的结果就会跟二维版对不上。

没有重叠子问题时，DP 只是把递归写成循环，白开一个数组：

// 每一步只依赖前两步 → 滚动变量即可，不必开 dp 数组
let prev2 = 0
let prev1 = 1
for (let i = 2; i <= n; i++) {
  const cur = prev1 + prev2
  prev2 = prev1
  prev1 = cur
}

// 判断标准：子问题会被重复求解吗？不会的话，递推就够了

五、不该上 DP 的情况​

没有重叠子问题时，DP 只是更慢的暴力——记忆化不会命中任何重复，等价于普通递归。另一种情况：贪心能成立就别上 DP。比如区间调度（按结束时间选最早）、跳跃游戏（能到的最远下标），贪心一步到位，比 DP 省一个数量级。先验证「贪心是否成立 / 是否有重叠子问题」，再决定要不要 DP。一个快速判别：状态能拆成「更小子问题且子问题重复出现」才值得 DP；每一步只依赖「当前最优局部选择」且局部最优能推出全局最优，那多半是贪心。

没有重叠子问题时，DP 只是更慢的暴力；贪心能解就别上 DP

六、状态定义不能随便换​

DP 不等于填表。填表只是实现，核心是状态定义与转移关系，递归写法同样是 DP。

能压维度也不代表就该压——压缩后丢失路径信息，需要还原具体方案时不能用。

更不是所有最值问题都该上 DP：没有重叠子问题时，它只是更慢的暴力，贪心能解就不要上 DP。

状态定义错了，转移方程怎么推都别扭——先认模型，再套实现。

从记忆化到递推的过渡，OI Wiki 动态规划 的引入部分写得比较顺，适合用来补齐基础。