动态规划方法论与面试进阶

动态规划不是记忆公式，而是把重复子问题的结果保存起来，并按照依赖关系构造最终答案。

何时考虑动态规划

一个问题通常需要具备两个特征：

• 重叠子问题：递归过程中会多次计算同一状态。
• 最优子结构：当前问题的答案可以由规模更小的子问题答案推导。

如果每个子问题只访问一次，普通分治可能已经足够；如果局部最优选择能保证全局最优，贪心可能更简单。

五步分析法

1. 定义状态：dp[i] 或 dp[i][j] 具体表示什么。
2. 写出转移：当前状态依赖哪些更小状态。
3. 确定初始值：最小问题的答案是什么。
4. 决定遍历顺序：确保计算当前状态前，依赖状态已经得到。
5. 检查答案位置与复杂度：最终读取哪个状态，能否压缩空间。

状态定义必须是一句完整、没有歧义的话。很多错误并不发生在代码阶段，而是状态含义从一开始就不明确。

示例：爬楼梯

每次可以走 1 或 2 级，求走到第 n 级的方案数。

• 状态：dp[i] 表示走到第 i 级的方案数。
• 转移：最后一步来自 i - 1 或 i - 2，所以 dp[i] = dp[i - 1] + dp[i - 2]。
• 初始值：dp[1] = 1，dp[2] = 2。

function climbStairs(n) {
  if (n <= 2) return n

  const dp = new Array(n + 1).fill(0)
  dp[1] = 1
  dp[2] = 2

  for (let step = 3; step <= n; step += 1) {
    dp[step] = dp[step - 1] + dp[step - 2]
  }

  return dp[n]
}

时间复杂度为 O(n)，空间复杂度为 O(n)。由于当前状态只依赖前两个状态，可以压缩到常数空间：

function climbStairs(n) {
  if (n <= 2) return n

  let previous = 1
  let current = 2

  for (let step = 3; step <= n; step += 1) {
    const next = previous + current
    previous = current
    current = next
  }

  return current
}

先写清晰版本并验证，再做空间压缩。过早压缩容易丢失状态含义。

自顶向下：记忆化搜索

递归天然对应问题定义时，可以先写搜索，再缓存已经计算的状态。

function climbStairs(n, memo = new Map()) {
  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
}

记忆化搜索只计算可达状态，代码通常接近递推定义；自底向上迭代没有递归栈，更容易控制遍历顺序和空间。

示例：最小路径和

给定非负整数网格，只能向右或向下移动，求从左上到右下的最小路径和。

• 状态：dp[row][column] 表示到达当前格子的最小路径和。
• 转移：从上方或左方进入，取较小值。

function minPathSum(grid) {
  const rows = grid.length
  const columns = grid[0].length
  const dp = Array.from({ length: rows }, () => new Array(columns).fill(0))

  dp[0][0] = grid[0][0]

  for (let row = 1; row < rows; row += 1) {
    dp[row][0] = dp[row - 1][0] + grid[row][0]
  }

  for (let column = 1; column < columns; column += 1) {
    dp[0][column] = dp[0][column - 1] + grid[0][column]
  }

  for (let row = 1; row < rows; row += 1) {
    for (let column = 1; column < columns; column += 1) {
      dp[row][column] = Math.min(
        dp[row - 1][column],
        dp[row][column - 1]
      ) + grid[row][column]
    }
  }

  return dp[rows - 1][columns - 1]
}

边界行和边界列只有一个来源，需要单独初始化。也可以增加一圈哨兵值，把边界逻辑统一进转移。

示例：0/1 背包

每件物品只能选择一次。weights[i] 是重量，values[i] 是价值，容量为 capacity。

二维状态可以定义为：前 i 件物品、容量为 c 时的最大价值。压缩为一维后：

function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0)

  for (let item = 0; item < weights.length; item += 1) {
    for (let current = capacity; current >= weights[item]; current -= 1) {
      dp[current] = Math.max(
        dp[current],
        dp[current - weights[item]] + values[item]
      )
    }
  }

  return dp[capacity]
}

容量必须倒序遍历，防止同一轮重复使用当前物品。完全背包允许重复选择物品，因此容量通常正序遍历。

遍历顺序的判断

不要死记正序或倒序，应从依赖关系推导：

• 当前行依赖上一行：外层遍历物品，内层遍历容量。
• 一维 0/1 背包：倒序，避免当前物品被重复使用。
• 一维完全背包：正序，允许使用本轮刚更新的状态。
• 求排列数：通常外层遍历容量，内层遍历选择。
• 求组合数：通常外层遍历选择，内层遍历容量。

从暴力搜索推导状态

拿到题目时先写“所有选择”的递归，往往比直接猜 dp 更可靠。递归参数描述一个子问题；如果不同路径会以相同参数进入同一子问题，就存在重叠状态。

以零钱兑换最少硬币为例，设 search(amount) 表示凑出剩余金额所需的最少硬币：

function coinChange(coins, amount) {
  const memo = new Map()

  function search(remaining) {
    if (remaining === 0) return 0
    if (remaining < 0) return Infinity
    if (memo.has(remaining)) return memo.get(remaining)

    let answer = Infinity

    for (const coin of coins) {
      answer = Math.min(answer, search(remaining - coin) + 1)
    }

    memo.set(remaining, answer)
    return answer
  }

  const result = search(amount)
  return Number.isFinite(result) ? result : -1
}

这里递归参数只有 remaining，因此状态维度也是金额。每个状态枚举 coins.length 个选择，状态数最多为 amount + 1，时间复杂度 O(amount × coins.length)，空间包含 memo 与递归栈。

推导流程是：暴力决策树 → 找重复递归参数 → 缓存参数组合 → 根据依赖方向改成迭代。不要先套题型名称，再反向解释一个不匹配的状态。

状态设计的常见维度

状态必须包含所有会影响未来答案的信息，又不能保留与未来无关的完整历史。常见设计包括：

• 前缀状态：前 i 个元素的答案，例如打家劫舍、序列划分。
• 双前缀状态：两个序列的前 i、j 个元素，例如最长公共子序列。
• 容量状态：处理到第 i 个选择且剩余/可用容量为 c。
• 区间状态：闭区间 [left, right] 的答案，例如区间合并、回文与矩阵链。
• 有限状态机：位置之外再记录持有、冷却、交易次数等有限业务状态。
• 树形状态：节点及“选/不选”等对子树未来有影响的状态。

判断状态是否充分，可以寻找反例：两个历史映射到同一状态后，它们面对相同未来选择是否一定拥有相同最优答案？如果不是，状态丢了信息；如果某个维度不影响未来，它可能冗余。

正确性证明：归纳与不变量

面试写出转移后，要说明它为什么覆盖且只覆盖所有合法方案。常用证明结构：

1. 状态语义：精确定义 dp[i]。
2. 基础情况：最小规模与定义一致。
3. 归纳假设：依赖的更小状态已经正确。
4. 分类讨论：按最后一步、最后一个选择或区间断点把所有方案分成互斥类别。
5. 最优性：每类使用正确子问题最优值，再在类别之间取 min/max/sum。

例如爬楼梯按最后一步是 1 级或 2 级分类，两类互斥且覆盖所有走法，所以方案数相加；最短路径从上或左进入，两类覆盖所有合法路径，目标是最小代价，所以取较小值。

循环实现还要维护不变量：开始计算 dp[i] 前，它依赖的状态均已计算且含义未改变。遍历顺序与一维压缩都应从这个不变量推出。

示例：最长公共子序列

给定两个字符串，求保持相对顺序但不要求连续的最长公共子序列长度。

• 状态：dp[i][j] 表示 first 前 i 个字符与 second 前 j 个字符的 LCS 长度。
• 若末尾字符相同，可以把它接到两个更短前缀的 LCS 后：dp[i][j] = dp[i - 1][j - 1] + 1。
• 若不同，至少舍弃一侧末尾：max(dp[i - 1][j], dp[i][j - 1])。

function longestCommonSubsequence(first, second) {
  const rows = first.length + 1
  const columns = second.length + 1
  const dp = Array.from({ length: rows }, () =>
    new Array(columns).fill(0)
  )

  for (let row = 1; row < rows; row += 1) {
    for (let column = 1; column < columns; column += 1) {
      if (first[row - 1] === second[column - 1]) {
        dp[row][column] = dp[row - 1][column - 1] + 1
      } else {
        dp[row][column] = Math.max(
          dp[row - 1][column],
          dp[row][column - 1]
        )
      }
    }
  }

  return dp[first.length][second.length]
}

时间和空间都是 O(mn)。只求长度时可以压缩空间；若要恢复具体序列，则保留完整表或额外决策信息，从右下角反向走：字符相同就选入，否则走向值较大的相邻状态。

示例：股票状态机

“每天持有或不持有”是有限状态机 DP。只允许一次交易时：

• cash：截至今天不持有股票的最大收益。
• hold：截至今天持有股票的最大收益。

function maxProfit(prices) {
  let cash = 0
  let hold = -Infinity

  for (const price of prices) {
    const previousCash = cash
    const previousHold = hold

    cash = Math.max(previousCash, previousHold + price)
    hold = Math.max(previousHold, -price)
  }

  return cash
}

hold = -price 表示唯一一次买入，不使用 previousCash - price，否则模型会允许多次交易。若允许多次、包含手续费、冷却期或最多 k 次交易，就在状态中加入相应约束。先定义状态机，再改转移，避免靠修改几行公式碰答案。

区间 DP 与遍历方向

区间状态 dp[left][right] 通常依赖更短区间，所以按区间长度从小到大遍历：

for (let length = 2; length <= n; length += 1) {
  for (let left = 0; left + length - 1 < n; left += 1) {
    const right = left + length - 1
    // 枚举断点或根据更短区间更新 dp[left][right]
  }
}

如果按 left 正序、right 正序直接填表，所需的内部区间可能尚未计算。遍历顺序不是代码风格，而是状态依赖拓扑排序。

空间压缩的条件

二维 DP 能否压缩，不只看“当前行依赖上一行”，还要判断当前行是否依赖自己，以及读取方向：

• 只依赖上一行相同或相邻列，可使用滚动数组。
• 一维数组原地更新时，正序会读到本轮新值，倒序会保留上一轮旧值。
• 若同时需要左上角旧值，可额外保存一个临时变量。
• 需要恢复方案时，压缩掉的历史可能必须用额外决策数组补回。

优化前先写二维版本，标注每个箭头依赖，再决定覆盖是否安全。空间从 O(mn) 降到 O(n) 时，通常选择较短维度作为数组宽度以进一步减少内存。

路径与方案恢复

DP 返回最优值不等于能返回具体选择。恢复方案常见两种方式：

1. 保留完整 dp 表，从答案状态根据转移等式反向判断上一个状态。
2. 填表时额外记录 choice[state] 或前驱，最后沿指针回溯。

多个选择同样最优时，题目可能要求任意一个、字典序最小或全部方案。tie-break 规则必须在转移和恢复中一致。输出全部方案可能本身具有指数规模，即使最优值能多项式时间求出，也不能承诺多项式总输出时间。

数值、不可达状态与工程边界

JavaScript number 是双精度浮点数，整数精确范围有限。组合计数可能快速超过 Number.MAX_SAFE_INTEGER；题目若要求取模，在每次加乘后取模，若要求精确大整数则使用 BigInt 并保持运算类型一致。

不可达状态根据目标选择哨兵：求最小值常用 Infinity，求最大值可用 -Infinity。但执行 Infinity + negativeValue 或在不同语言中使用最大整数再相加都要谨慎。初始化值必须和“空选择是否合法”一致。

生产输入还要处理空数组、非法容量、巨大二维表导致的内存峰值和递归栈上限。算法复杂度应结合 JavaScript 数组对象开销，而不只计算元素个数。

面试表达模板

1. 复述输入、输出、限制与可修改性，确认空输入语义。
2. 先给暴力选择与复杂度，指出重复子问题。
3. 用完整句子定义状态和每个维度。
4. 按最后一步/选择证明转移覆盖全部情况。
5. 写初始化和遍历顺序，边写边维护不变量。
6. 用最小样例手推两三个状态。
7. 给出时间、空间复杂度，再讨论是否能压缩和恢复方案。

资深面试还应主动说明约束变化如何影响模型。例如“如果元素允许重复选择，容量遍历方向改变”“如果要输出路径，需要保留前驱”“如果输入规模达到十万，O(n²) 不可接受，需要寻找单调性、二分或不同算法”。

资深面试追问

动态规划和贪心有什么区别？

DP 保留足够状态并比较所有必要选择，利用重叠子问题降低重复计算；贪心只做当前局部选择，不回看。贪心必须证明交换性质或局部最优可扩展为全局最优。能用 DP 不代表贪心成立，贪心成立时通常更省时空。（深入阅读：何时考虑动态规划、区间贪心的选择依据）

记忆化搜索和递推如何选择？

两者状态和渐进复杂度通常相同。记忆化贴近递归定义、只访问可达状态，但有函数与栈开销；递推需要明确拓扑顺序，内存更可控并便于压缩。稀疏状态或复杂搜索优先记忆化，规则网格和大深度常优先迭代。（深入阅读：自顶向下记忆化搜索）

如何判断 DP 状态设计错了？

若相同状态参数下未来答案仍依赖不同历史，说明状态不足；若转移不得不读取没有体现在状态中的全局过程，也可能丢维度；若很多维度从不影响后续选择，则可能冗余。用两个映射到同状态但答案不同的反例最有说服力。（深入阅读：状态设计的常见维度）

为什么 0/1 背包一维数组要倒序？

一维数组同时代表上一轮和当前轮。正序时 dp[c - weight] 可能已经在本轮使用当前物品更新，再加一次就重复选择；倒序确保所读的小容量仍是上一轮结果。完全背包正序正是为了允许本轮重复使用。（深入阅读：遍历顺序的判断）

常见错误

• 状态定义含糊，代码中途改变 dp[i] 的含义。
• 初始值与状态语义不一致。
• 循环边界遗漏 0、n 或空输入。
• 先做空间压缩，却没有保留上一层仍需使用的数据。
• 把不可达状态初始化为 0，导致它被误认为合法答案。
• 只输出答案，不用小规模输入打印 DP 表验证转移。

解题检查

• 能用一句话准确解释每个维度的含义。
• 每个转移分支都对应一种互斥或可枚举的选择。
• 初始状态覆盖空集合、第一行或第一列等边界。
• 遍历顺序满足所有数据依赖。
• 能说明时间与空间复杂度，以及空间压缩为何成立。
• 用最小输入、普通输入和边界输入分别验证结果。
• 能用归纳或循环不变量解释正确性，不只给出公式。
• 需要输出具体方案时保留了足够的前驱或决策信息。
• 计数问题评估了安全整数、取模和内存上限。