动态规划入门

把重叠子问题与最优子结构转化为状态转移。代码继续用 JavaScript。

相关：递归与回溯 · 贪心。

1. 什么是动态规划

动态规划（DP）：把大问题拆成子问题，保存子问题答案，避免重复计算，再拼出原问题答案。

适合问：

• 最优值（最大 / 最小）
• 方案数
• 可行性（能否凑成）

不适合硬套 DP：必须列出所有路径细节且状态爆炸、或根本无重叠子问题——这时更像纯回溯 / 搜索。

2. 重叠子问题与最优子结构

性质	含义
重叠子问题	不同大问题会反复算到同一子问题（如 fib(n-2)）
最优子结构	原问题最优解可由子问题最优解推出

// 朴素递归：大量重复计算 → 指数时间
function fibNaive(n) {
  if (n <= 1) return n
  return fibNaive(n - 1) + fibNaive(n - 2)
}

fib(5) 会多次算 fib(3)、fib(2)——这就是重叠。DP / 记忆化把每个 n 只算一次。

没有最优子结构时（局部最优拼不出全局最优，又必须枚举组合），不要假装能转移。

3. 状态定义与转移方程

做题四步：

1. 状态是什么（dp[i] / dp[i][j] 表示啥）
2. 转移怎么走（依赖哪些更小状态）
3. 初始值（边界）
4. 答案在哪（dp[n] 还是 max(dp)）

以爬楼梯为例：一次 1 或 2 阶，到 n 阶有多少种走法。

• 状态：dp[i] = 爬到第 i 阶的方法数
• 转移：dp[i] = dp[i-1] + dp[i-2]
• 初始：dp[1]=1, dp[2]=2
• 答案：dp[n]

状态定义错了，后面全错；优先想「我要求的答案能不能成为某个 dp[...]」。

4. 自顶向下（记忆化）与自底向上

自顶向下：递归 + 缓存

function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n
  if (memo.has(n)) return memo.get(n)
  const val = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
  memo.set(n, val)
  return val
}

好处：怎么想问题就怎么写；只算用到的状态。注意递归栈深度。

自底向上：迭代填表

function fibDp(n) {
  if (n <= 1) return n
  const dp = new Array(n + 1)
  dp[0] = 0
  dp[1] = 1
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

好处：无栈风险、顺序清晰，面试更常见。两者本质相同，都是「每个状态算一次」。

5. 一维 DP 典型题

爬楼梯 / 斐波那契型

见上，O(n) 时间、O(n) 空间（可再压到 O(1)）。

打家劫舍

偷到第 i 家：偷这家则不能偷 i-1，或不偷这家。

// nums[i] = 第 i 家财物
function rob(nums) {
  if (nums.length === 0) return 0
  if (nums.length === 1) return nums[0]
  const dp = new Array(nums.length)
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
  }
  return dp[nums.length - 1]
}

零钱兑换（最少硬币数）

完全背包味道：dp[a] = 凑成金额 a 的最少硬币。

function coinChange(coins, amount) {
  const INF = amount + 1
  const dp = new Array(amount + 1).fill(INF)
  dp[0] = 0
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a >= c) dp[a] = Math.min(dp[a], dp[a - c] + 1)
    }
  }
  return dp[amount] > amount ? -1 : dp[amount]
}

一维常见形态：线性递推、背包压缩成一维、以某个下标为结尾的最优。

6. 二维 DP 入门

路径数 / 最小路径和

网格从左上到右下，只能向右或向下。

// 唯一路径数：m 行 n 列
function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(0))
  for (let i = 0; i < m; i++) dp[i][0] = 1
  for (let j = 0; j < n; j++) dp[0][j] = 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]
}

最长公共子序列（LCS）

function longestCommonSubsequence(text1, text2) {
  const m = text1.length
  const n = text2.length
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
  return dp[m][n]
}

0-1 背包（入门必会）

dp[i][w] = 前 i 个物品、容量 w 时的最大价值。

function knapsack(weights, values, W) {
  const n = weights.length
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0))
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w] // 不选
      if (w >= weights[i - 1]) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1], // 选
        )
      }
    }
  }
  return dp[n][W]
}

二维直觉：一维不够表达「两个自变量」（位置 i 与 j、物品与容量）。

7. 空间优化思路

转移若只依赖「上一层」或「前几个」，可压维度。

// 爬楼梯：只依赖前两项 → O(1) 空间
function climbStairs(n) {
  if (n <= 2) return n
  let a = 1
  let b = 2
  for (let i = 3; i <= n; i++) {
    const c = a + b
    a = b
    b = c
  }
  return b
}

// 0-1 背包压成一维：必须逆序枚举容量，避免本轮物品被重复用
function knapsack1D(weights, values, W) {
  const dp = new Array(W + 1).fill(0)
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }
  return dp[W]
}

注意：

• 0-1 背包一维：容量从大到小
• 完全背包一维：容量从小到大（可重复用）
• 先写对二维，再压空间，少踩坑

---

上手顺序建议：斐波那契 / 爬楼梯 → 打家劫舍 → 网格路径 → 0-1 背包 → LCS / 零钱。状态定义能口述清楚，再写循环。

上一篇：贪心 · 下一篇：图论基础