主题
动态规划深度解析
面向前端/全栈工程师的动态规划完整攻略：原理讲解 → ASCII 图解 → 完整可运行代码 → 复杂度分析 → 面试实战
涵盖 DP 核心思想、解题五步法、背包问题、子序列、字符串 DP、路径问题、股票问题、区间 DP 等经典高频题
一、动态规划核心思想
1.1 什么是动态规划
动态规划（Dynamic Programming，简称 DP）是一种通过将原问题拆解为相互重叠的子问题，并存储子问题的解以避免重复计算来求解最优化问题的算法思想。
DP 成立的三大条件：
┌─────────────────────────────────────────────────────────────────┐
│ 动态规划三大核心性质 │
├─────────────────────┬───────────────────────────────────────────┤
│ 最优子结构 │ 问题的最优解包含子问题的最优解 │
│ (Optimal │ 即：可以从子问题的最优解推导出原问题的最优解 │
│ Substructure) │ │
├─────────────────────┼───────────────────────────────────────────┤
│ 重叠子问题 │ 递归求解时会反复遇到相同的子问题 │
│ (Overlapping │ 即：不同的决策路径会到达同一个子状态 │
│ Subproblems) │ │
├─────────────────────┼───────────────────────────────────────────┤
│ 无后效性 │ 某阶段的状态一旦确定，之后的过程不受之前 │
│ (No Aftereffect) │ 决策路径的影响，只与当前状态有关 │
└─────────────────────┴───────────────────────────────────────────┘以斐波那契数列为例理解重叠子问题：
fib(5)
/ \
fib(4) fib(3) ← fib(3) 被计算了 2 次
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← fib(2) 被计算了 3 次
/ \
fib(2) fib(1)
不使用 DP：指数级重复计算 O(2^n)
使用 DP：每个子问题只算一次 O(n)1.2 DP vs 贪心 vs 分治
┌──────────┬──────────────────┬──────────────────┬──────────────────┐
│ 特征 │ 动态规划 │ 贪心算法 │ 分治算法 │
├──────────┼──────────────────┼──────────────────┼──────────────────┤
│ 子问题 │ 重叠（大量重复） │ 无需回溯子问题 │ 不重叠（互相独立）│
│ 最优解 │ 全局最优（穷举） │ 局部最优→全局最优 │ 合并子问题的解 │
│ 决策方式 │ 枚举所有选择取最优 │ 每步选当前最优 │ 拆分→递归→合并 │
│ 时间复杂度│ 多项式级 │ 通常更快 │ 取决于合并代价 │
│ 典型问题 │ 背包、最长子序列 │ 活动选择、Huffman │ 归并排序、快排 │
│ 回溯需求 │ 需要（比较所有） │ 不需要 │ 不需要 │
└──────────┴──────────────────┴──────────────────┴──────────────────┘关键区别：
- 贪心只做一次选择，不回头看；DP 会枚举所有可能的选择，取最优
- 分治的子问题互不相干（如归并排序的左右半段）；DP 的子问题高度重叠
- 如果贪心策略能被证明正确，优先用贪心（更简单高效）；否则用 DP
1.3 自顶向下 vs 自底向上
┌─────────────────────────────────────────────────────────────┐
│ 自顶向下（记忆化递归）Top-Down │
├─────────────────────────────────────────────────────────────┤
│ 思路：从原问题出发，递归拆解，遇到计算过的子问题直接返回缓存 │
│ 实现：递归 + 哈希表/数组缓存 │
│ 优点：只计算需要的子问题，代码直观 │
│ 缺点：递归调用栈开销，可能栈溢出 │
└─────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────┐
│ 自底向上（递推/迭代）Bottom-Up │
├─────────────────────────────────────────────────────────────┤
│ 思路：从最小的子问题开始，逐步推导到原问题 │
│ 实现：for 循环 + DP 数组 │
│ 优点：无递归开销，可做空间优化（滚动数组） │
│ 缺点：需要想清楚遍历顺序，可能计算无用子问题 │
└─────────────────────────────────────────────────────────────┘
执行顺序对比（以 fib(5) 为例）:
自顶向下: fib(5) → fib(4) → fib(3) → fib(2) → fib(1) → fib(0)
↑ 递归展开方向 ↑ base case
遇到已缓存的直接返回
自底向上: fib(0) → fib(1) → fib(2) → fib(3) → fib(4) → fib(5)
↑ base case ↑ 目标
从小到大逐步填表二、解题五步法
┌─────────────────────────────────────────────────────────────┐
│ DP 解题五步法 │
│ │
│ Step 1 定义状态 → dp[i] 或 dp[i][j] 代表什么？ │
│ (最关键的一步！) │
│ │
│ Step 2 写出转移方程 → dp[i] 和 dp[i-1]... 的关系是什么？ │
│ (问题的核心递推逻辑) │
│ │
│ Step 3 确定初始条件 → base case 是什么？ │
│ dp[0] = ? dp[1] = ? │
│ │
│ Step 4 确定遍历顺序 → 从前往后？从后往前？双层循环方向？ │
│ (确保计算 dp[i] 时依赖项已计算) │
│ │
│ Step 5 空间优化 → 能否用滚动变量替代整个数组？ │
│ 二维能否压缩到一维？ │
└─────────────────────────────────────────────────────────────┘三、基础题目
3.1 斐波那契数列
状态定义：dp[i] 表示第 i 个斐波那契数
转移方程：dp[i] = dp[i-1] + dp[i-2]
初始条件：dp[0] = 0, dp[1] = 1
dp 表填写过程:
i: 0 1 2 3 4 5 6 7 8
dp[i]: 0 1 1 2 3 5 8 13 21
↑ ↑
base case
↑
dp[2] = dp[1] + dp[0] = 1 + 0 = 1
↑
dp[3] = dp[2] + dp[1] = 1 + 1 = 2typescript
function fib(n: number): number {
if (n <= 1) return n
let prev2 = 0
let prev1 = 1
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2
prev2 = prev1
prev1 = curr
}
return prev1
}
console.log(fib(10)) // 55复杂度：时间 O(n)，空间 O(1)
3.2 爬楼梯（LeetCode 70）
每次可以爬 1 或 2 个台阶，问爬到第 n 阶有几种方法？
状态定义：dp[i] 表示爬到第 i 阶的方法总数
转移方程：dp[i] = dp[i-1] + dp[i-2]（最后一步要么从 i-1 爬 1 阶，要么从 i-2 爬 2 阶）
初始条件：dp[0] = 1, dp[1] = 1
决策树（n=4）:
0
/ \
1 2
/ \ / \
2 3 3 4 ✓
/ \ | |
3 4 4 4 ✓
| ✓ ✓
4
✓
dp 表:
i: 0 1 2 3 4 5
dp[i]: 1 1 2 3 5 8
↑
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
(走法: 1+1, 2)
↑
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
(走法: 1+1+1, 1+2, 2+1)解法演进一：暴力递归
typescript
function climbStairsRecursive(n: number): number {
if (n <= 1) return 1
return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2)
}复杂度：时间 O(2^n)，空间 O(n)（递归栈）。存在大量重复计算。
解法演进二：记忆化递归（自顶向下）
typescript
function climbStairsMemo(n: number): number {
const memo = new Map<number, number>()
function dp(i: number): number {
if (i <= 1) return 1
if (memo.has(i)) return memo.get(i)!
const result = dp(i - 1) + dp(i - 2)
memo.set(i, result)
return result
}
return dp(n)
}复杂度：时间 O(n)，空间 O(n)
解法演进三：自底向上 DP
typescript
function climbStairsDP(n: number): number {
const dp = new Array(n + 1)
dp[0] = 1
dp[1] = 1
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}复杂度：时间 O(n)，空间 O(n)
解法演进四：空间优化
typescript
function climbStairs(n: number): number {
if (n <= 1) return 1
let prev2 = 1
let prev1 = 1
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2
prev2 = prev1
prev1 = curr
}
return prev1
}
console.log(climbStairs(4)) // 5
console.log(climbStairs(5)) // 8复杂度：时间 O(n)，空间 O(1)
演进总结:
暴力递归 → 记忆化递归 → 自底向上 DP → 空间优化
O(2^n)/O(n) O(n)/O(n) O(n)/O(n) O(n)/O(1)
↓ ↓ ↓ ↓
重复计算 缓存消除重复 去掉递归栈 只保留两个变量四、背包问题系列
4.1 0/1 背包
问题：有 n 个物品，每个物品有重量 w[i] 和价值 v[i]。背包容量为 W，每个物品只能选或不选，求能装入的最大价值。
状态定义：dp[i][j] 表示前 i 个物品、背包容量为 j 时的最大价值
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 当 j >= w[i]
dp[i][j] = dp[i-1][j] 当 j < w[i]dp[i-1][j]：不选第 i 个物品dp[i-1][j-w[i]] + v[i]：选第 i 个物品
初始条件：dp[0][j] = 0（没有物品可选，价值为 0）
ASCII 图解
物品: [{w:1, v:1}, {w:2, v:6}, {w:3, v:10}, {w:2, v:9}]
背包容量 W = 5
填表过程 dp[i][j]:
容量j→ 0 1 2 3 4 5
物品i↓
0 (无物品) 0 0 0 0 0 0
1 (w=1,v=1) 0 1 1 1 1 1
2 (w=2,v=6) 0 1 6 7 7 7
3 (w=3,v=10) 0 1 6 10 11 16
4 (w=2,v=9) 0 1 6 10 15 16
以 dp[3][5] = 16 为例:
不选物品3: dp[2][5] = 7
选物品3: dp[2][5-3] + 10 = dp[2][2] + 10 = 6 + 10 = 16
max(7, 16) = 16 ✓
以 dp[4][4] = 15 为例:
不选物品4: dp[3][4] = 11
选物品4: dp[3][4-2] + 9 = dp[3][2] + 9 = 6 + 9 = 15
max(11, 15) = 15 ✓二维 DP 实现
typescript
function knapsack01_2D(weights: number[], values: number[], capacity: number): number {
const n = weights.length
const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0))
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= capacity; j++) {
dp[i][j] = dp[i - 1][j]
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
}
}
}
return dp[n][capacity]
}
console.log(knapsack01_2D([1, 2, 3, 2], [1, 6, 10, 9], 5)) // 16一维优化
关键观察：dp[i][j] 只依赖 dp[i-1][...]（上一行），因此可以压缩为一维数组。
注意：一维时必须从右往左遍历容量，保证使用的是上一行的值（未被本轮更新的值）。
一维优化遍历顺序（从右往左）:
j: 0 1 2 3 4 5
←←←←←←←←←←←←←←←←←←← 方向
如果从左往右: dp[j-w[i]] 已经被本轮更新过，
相当于物品 i 被重复使用了（变成完全背包！）typescript
function knapsack01(weights: number[], values: number[], capacity: number): number {
const dp = new Array(capacity + 1).fill(0)
for (let i = 0; i < weights.length; i++) {
for (let j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i])
}
}
return dp[capacity]
}
console.log(knapsack01([1, 2, 3, 2], [1, 6, 10, 9], 5)) // 16复杂度：时间 O(n × W)，空间 O(W)
4.2 完全背包
问题：与 0/1 背包类似，但每个物品可以无限次选取。
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])注意与 0/1 背包的区别：选第 i 个物品时从 dp[i][...] 取值（而非 dp[i-1][...]），因为同一物品可以再次选取。
一维优化时从左往右遍历（正好与 0/1 背包相反）：
0/1 背包: j 从右往左 → 保证每个物品只用一次
完全背包: j 从左往右 → 允许同一物品重复使用typescript
function knapsackComplete(weights: number[], values: number[], capacity: number): number {
const dp = new Array(capacity + 1).fill(0)
for (let i = 0; i < weights.length; i++) {
for (let j = weights[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i])
}
}
return dp[capacity]
}
console.log(knapsackComplete([1, 2, 3], [2, 5, 8], 5)) // 13复杂度：时间 O(n × W)，空间 O(W)
4.3 分割等和子集（LeetCode 416）
给定一个只包含正整数的非空数组，判断是否可以将其分割为两个子集，使两个子集的元素和相等。
转化为 0/1 背包：能否从数组中选若干个数，使得和恰好为 sum / 2。
状态定义：dp[j] 表示能否恰好凑出和为 j
转移方程：dp[j] = dp[j] || dp[j - nums[i]]
初始条件：dp[0] = true
示例: nums = [1, 5, 11, 5], sum = 22, target = 11
dp 表填写 (true=T, false=F):
j→ 0 1 2 3 4 5 6 7 8 9 10 11
初始 T F F F F F F F F F F F
num=1 T T F F F F F F F F F F
num=5 T T F F F T T F F F F F
num=11 T T F F F T T F F F F T
num=5 T T F F F T T F F F T T ← dp[11]=T ✓
答案: true (子集 {1,5,5} 和 {11})typescript
function canPartition(nums: number[]): boolean {
const sum = nums.reduce((a, b) => a + b, 0)
if (sum % 2 !== 0) return false
const target = sum / 2
const dp = new Array(target + 1).fill(false)
dp[0] = true
for (const num of nums) {
for (let j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num]
}
}
return dp[target]
}
console.log(canPartition([1, 5, 11, 5])) // true
console.log(canPartition([1, 2, 3, 5])) // false复杂度：时间 O(n × sum/2)，空间 O(sum/2)
五、子序列系列
5.1 最长递增子序列 LIS（LeetCode 300）
给定一个整数数组 nums，找到其中最长严格递增子序列的长度。
解法一：O(n²) DP
状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
转移方程：dp[i] = max(dp[j] + 1)，其中 0 ≤ j < i 且 nums[j] < nums[i]
初始条件：dp[i] = 1（每个元素自身构成长度为 1 的子序列）
nums = [10, 9, 2, 5, 3, 7, 101, 18]
i=0: nums[0]=10 dp=[1]
i=1: nums[1]=9 无 j 满足 nums[j]<9 dp=[1,1]
i=2: nums[2]=2 无 j 满足 nums[j]<2 dp=[1,1,1]
i=3: nums[3]=5 j=2: 2<5 → dp[3]=dp[2]+1=2 dp=[1,1,1,2]
i=4: nums[4]=3 j=2: 2<3 → dp[4]=dp[2]+1=2 dp=[1,1,1,2,2]
i=5: nums[5]=7 j=2: 2<7 → 2, j=3: 5<7 → 3, j=4: 3<7 → 3
dp[5]=3 dp=[1,1,1,2,2,3]
i=6: nums[6]=101 最大 dp[j]+1=4 dp=[1,1,1,2,2,3,4]
i=7: nums[7]=18 j=5: 7<18 → dp[5]+1=4 dp=[1,1,1,2,2,3,4,4]
答案: max(dp) = 4, 子序列: [2, 5, 7, 101] 或 [2, 3, 7, 101] 等typescript
function lengthOfLIS_DP(nums: number[]): number {
const n = nums.length
const dp = new Array(n).fill(1)
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
return Math.max(...dp)
}
console.log(lengthOfLIS_DP([10, 9, 2, 5, 3, 7, 101, 18])) // 4复杂度：时间 O(n²)，空间 O(n)
解法二：O(n log n) 贪心 + 二分查找
核心思想：维护一个数组 tails，tails[i] 表示长度为 i+1 的所有递增子序列的最小末尾元素。
- 如果当前元素大于
tails末尾，追加 - 否则二分查找替换第一个 ≥ 当前元素的位置
nums = [10, 9, 2, 5, 3, 7, 101, 18]
处理 10: tails = [10]
处理 9: 9 < 10, 替换 → tails = [9]
处理 2: 2 < 9, 替换 → tails = [2]
处理 5: 5 > 2, 追加 → tails = [2, 5]
处理 3: 3 < 5, 替换 → tails = [2, 3]
处理 7: 7 > 3, 追加 → tails = [2, 3, 7]
处理 101: 101 > 7,追加 → tails = [2, 3, 7, 101]
处理 18: 18 < 101,替换 → tails = [2, 3, 7, 18]
tails 长度 = 4，即 LIS 长度 = 4typescript
function lengthOfLIS(nums: number[]): number {
const tails: number[] = []
for (const num of nums) {
let lo = 0
let hi = tails.length
while (lo < hi) {
const mid = (lo + hi) >> 1
if (tails[mid] < num) {
lo = mid + 1
} else {
hi = mid
}
}
tails[lo] = num
}
return tails.length
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) // 4复杂度：时间 O(n log n)，空间 O(n)
5.2 最长公共子序列 LCS（LeetCode 1143）
给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。
状态定义：dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
转移方程：
若 text1[i-1] === text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])初始条件：dp[0][j] = 0, dp[i][0] = 0
ASCII 图解 DP 表填写
text1 = "abcde", text2 = "ace"
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
填表过程详解:
dp[1][1]: text1[0]='a' == text2[0]='a' → dp[0][0]+1 = 1 ↖+1
dp[1][2]: text1[0]='a' != text2[1]='c' → max(dp[0][2], dp[1][1]) = max(0,1) = 1
dp[3][2]: text1[2]='c' == text2[1]='c' → dp[2][1]+1 = 2 ↖+1
dp[5][3]: text1[4]='e' == text2[2]='e' → dp[4][2]+1 = 3 ↖+1
回溯路径 (箭头 ↖ 表示取对角线，即两字符匹配):
"" a c e
"" 0 0 0 0
a 0 1↖ 1← 1←
b 0 1↑ 1↑ 1↑
c 0 1↑ 2↖ 2←
d 0 1↑ 2↑ 2↑
e 0 1↑ 2↑ 3↖
LCS = "ace", 长度 = 3typescript
function longestCommonSubsequence(text1: string, text2: string): number {
const m = text1.length
const n = text2.length
const dp: number[][] = 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]
}
console.log(longestCommonSubsequence("abcde", "ace")) // 3
console.log(longestCommonSubsequence("abc", "def")) // 0复杂度：时间 O(m × n)，空间 O(m × n)，可优化至 O(min(m, n))
六、字符串 DP：编辑距离（LeetCode 72）
给定两个字符串 word1 和 word2，返回将 word1 转换为 word2 所需的最少操作次数。允许的操作：插入、删除、替换一个字符。
状态定义：dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数
转移方程：
若 word1[i-1] === word2[j-1]:
dp[i][j] = dp[i-1][j-1] (字符相同，无需操作)
否则:
dp[i][j] = 1 + min(
dp[i-1][j], (删除 word1[i-1])
dp[i][j-1], (插入 word2[j-1])
dp[i-1][j-1] (替换 word1[i-1] → word2[j-1])
)初始条件：dp[i][0] = i（删 i 次），dp[0][j] = j（插 j 次）
ASCII 图解
word1 = "horse", word2 = "ros"
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
填表关键步骤:
dp[1][1]: 'h' != 'r' → 1 + min(dp[0][1], dp[1][0], dp[0][0])
= 1 + min(1, 1, 0) = 1 (替换 h→r)
dp[2][2]: 'o' == 'o' → dp[1][1] = 1 (字符匹配，直接取对角线)
dp[5][3]: 'e' != 's' → 1 + min(dp[4][3], dp[5][2], dp[4][2])
= 1 + min(2, 4, 3) = 3
答案: dp[5][3] = 3
操作序列: horse → rorse (替换 h→r) → rose (删除 r) → ros (删除 e)typescript
function minDistance(word1: string, word2: string): number {
const m = word1.length
const n = word2.length
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
for (let i = 0; i <= m; i++) dp[i][0] = i
for (let j = 0; j <= n; j++) dp[0][j] = j
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
}
}
}
return dp[m][n]
}
console.log(minDistance("horse", "ros")) // 3
console.log(minDistance("intention", "execution")) // 5复杂度：时间 O(m × n)，空间 O(m × n)
七、路径问题
7.1 不同路径（LeetCode 62）
一个机器人位于 m × n 网格的左上角，每次只能向下或向右移动一步，问到达右下角共有多少条不同路径？
状态定义：dp[i][j] 表示到达位置 (i, j) 的不同路径数
转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始条件：dp[0][j] = 1, dp[i][0] = 1（第一行和第一列只有一条路径）
m=3, n=4 的 DP 表:
0 1 2 3
0 [ 1 1 1 1 ]
1 [ 1 2 3 4 ]
2 [ 1 3 6 10 ]
dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10
路径可视化 (3×4 网格):
┌───┬───┬───┬───┐
│ S → → → │
│ ↓ ↓ ↓ ↓ │
│ → → → │
│ ↓ ↓ ↓ ↓ │
│ → → → E │
└───┴───┴───┴───┘typescript
function uniquePaths(m: number, n: number): number {
const dp = new Array(n).fill(1)
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1]
}
}
return dp[n - 1]
}
console.log(uniquePaths(3, 4)) // 10
console.log(uniquePaths(3, 7)) // 28复杂度：时间 O(m × n)，空间 O(n)
7.2 最小路径和（LeetCode 64）
给定一个 m × n 的网格，每个格子有一个非负整数，找到从左上角到右下角的路径，使得路径上的数字总和最小。
状态定义：dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和
转移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
初始条件：dp[0][0] = grid[0][0]，首行/首列逐步累加
grid: dp 表:
[1, 3, 1] [1, 4, 5]
[1, 5, 1] [2, 7, 6]
[4, 2, 1] [6, 8, 7] ← 答案
dp[1][1] = 5 + min(dp[0][1], dp[1][0]) = 5 + min(4, 2) = 7
dp[2][2] = 1 + min(dp[1][2], dp[2][1]) = 1 + min(6, 8) = 7
最小路径: 1 → 3 → 1 → 1 → 1 = 7
↓ → → ↓
或 1 → 1 → 5 → 1 → 1（不对，这是另一条路径）
实际: 1→3→1→1→1，路径为 右→右→下→下→... 不对
正确路径: (0,0)→(1,0)→(1,1)→(1,2)→(2,2) = 1+1+5+1+1=9
或: (0,0)→(0,1)→(0,2)→(1,2)→(2,2) = 1+3+1+1+1=7 ✓typescript
function minPathSum(grid: number[][]): number {
const m = grid.length
const n = grid[0].length
const dp = new Array(n).fill(0)
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 && j === 0) {
dp[j] = grid[0][0]
} else if (i === 0) {
dp[j] = dp[j - 1] + grid[i][j]
} else if (j === 0) {
dp[j] = dp[j] + grid[i][j]
} else {
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]
}
}
}
return dp[n - 1]
}
console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) // 7复杂度：时间 O(m × n)，空间 O(n)
八、股票问题
8.1 买卖股票的最佳时机（LeetCode 121）
只能买卖一次，求最大利润。
状态机思路：每天有两种状态——持有股票和不持有股票。
状态机:
买入(buy)
[不持有] ─────→ [持有]
↑ │
│ 卖出(sell) │
└───────────────┘
│
└─ 不操作(rest) ─→ 保持不持有
[持有] ─ 不操作(rest) ─→ 保持持有状态定义：
hold：第 i 天结束时持有股票的最大收益notHold：第 i 天结束时不持有股票的最大收益
转移方程：
hold[i] = max(hold[i-1], -prices[i]) (保持持有 / 今天买入)
notHold[i] = max(notHold[i-1], hold[i-1] + prices[i]) (保持不持有 / 今天卖出)prices = [7, 1, 5, 3, 6, 4]
day price hold notHold
0 7 -7 0
1 1 -1 0
2 5 -1 4 ← 第1天买(1), 第2天卖(5), 利润4
3 3 -1 4
4 6 -1 5 ← 第1天买(1), 第4天卖(6), 利润5 ✓
5 4 -1 5
答案: notHold = 5typescript
function maxProfit121(prices: number[]): number {
let hold = -Infinity
let notHold = 0
for (const price of prices) {
hold = Math.max(hold, -price)
notHold = Math.max(notHold, hold + price)
}
return notHold
}
console.log(maxProfit121([7, 1, 5, 3, 6, 4])) // 5复杂度：时间 O(n)，空间 O(1)
8.2 买卖股票的最佳时机 II（LeetCode 122）
可以多次买卖（但同一时间只能持有一股），求最大利润。
状态定义同上，转移方程改变：
hold[i] = max(hold[i-1], notHold[i-1] - prices[i]) (可以在已有利润基础上再买)
notHold[i] = max(notHold[i-1], hold[i-1] + prices[i])与 121 的区别：买入时从 notHold[i-1] 而非 0 出发（因为之前可以有收益）。
prices = [7, 1, 5, 3, 6, 4]
day price hold notHold
0 7 -7 0
1 1 -1 0
2 5 -1 4
3 3 1 4 ← hold = notHold(4) - price(3) = 1
4 6 1 7 ← notHold = hold(1) + price(6) = 7
5 4 3 7
答案: 7 (买1卖5利润4, 买3卖6利润3, 共7)typescript
function maxProfit122(prices: number[]): number {
let hold = -Infinity
let notHold = 0
for (const price of prices) {
const prevHold = hold
hold = Math.max(hold, notHold - price)
notHold = Math.max(notHold, prevHold + price)
}
return notHold
}
console.log(maxProfit122([7, 1, 5, 3, 6, 4])) // 7
console.log(maxProfit122([1, 2, 3, 4, 5])) // 4复杂度：时间 O(n)，空间 O(1)
九、区间 DP 简介：戳气球（LeetCode 312）
有 n 个气球，编号 0 到 n-1，每个气球上有一个数字。每次戳破一个气球 i，获得
nums[left] * nums[i] * nums[right]金币（left 和 right 是 i 的相邻未戳破气球），求最多能获得多少金币。
区间 DP 的核心思想：枚举一个区间内最后被戳破的气球。
关键转换：在 nums 两端各添加一个值为 1 的虚拟气球，变为 [1, nums[0], ..., nums[n-1], 1]。
状态定义：dp[i][j] 表示戳破 (i, j) 开区间内所有气球能获得的最大金币
转移方程：
dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
其中 i < k < j，k 是该区间内最后被戳破的气球为什么是"最后戳破"？
如果 k 是 (i,j) 内最后一个被戳破的，那么：
- (i,k) 和 (k,j) 内的气球已经全部戳完
- 戳 k 时，其左右邻居恰好是 i 和 j（边界气球）
- 得分 = dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
遍历顺序：区间长度从小到大
示例: nums = [3, 1, 5, 8] → 扩展为 [1, 3, 1, 5, 8, 1]
区间长度 len=2 (只有一个气球可戳):
dp[0][2] = 1*3*1 = 3 (戳3)
dp[1][3] = 3*1*5 = 15 (戳1)
dp[2][4] = 1*5*8 = 40 (戳5)
dp[3][5] = 5*8*1 = 40 (戳8)
区间长度 len=3:
dp[0][3]: k=1: dp[0][1]+dp[1][3]+1*3*5 = 0+15+15 = 30
k=2: dp[0][2]+dp[2][3]+1*1*5 = 3+0+5 = 8
max = 30
...
最终: dp[0][5] = 167typescript
function maxCoins(nums: number[]): number {
const n = nums.length
const vals = [1, ...nums, 1]
const dp: number[][] = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0))
for (let len = 2; len <= n + 1; len++) {
for (let i = 0; i + len <= n + 1; i++) {
const j = i + len
for (let k = i + 1; k < j; k++) {
dp[i][j] = Math.max(
dp[i][j],
dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j]
)
}
}
}
return dp[0][n + 1]
}
console.log(maxCoins([3, 1, 5, 8])) // 167复杂度：时间 O(n³)，空间 O(n²)
十、面试题精选（5 道）
题目 1：零钱兑换（LeetCode 322）
给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币个数。如果无法凑成，返回 -1。
解答：
这是一个完全背包问题的变体。
状态定义：dp[j] 表示凑出金额 j 所需的最少硬币数
转移方程：dp[j] = min(dp[j], dp[j - coin] + 1)
初始条件：dp[0] = 0，其余为 Infinity
coins = [1, 2, 5], amount = 11
j: 0 1 2 3 4 5 6 7 8 9 10 11
初始: 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
coin=1: 0 1 2 3 4 5 6 7 8 9 10 11
coin=2: 0 1 1 2 2 3 3 4 4 5 5 6
coin=5: 0 1 1 2 2 1 2 2 3 3 2 3
答案: dp[11] = 3 (5 + 5 + 1)typescript
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity)
dp[0] = 0
for (const coin of coins) {
for (let j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1)
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
}
console.log(coinChange([1, 2, 5], 11)) // 3
console.log(coinChange([2], 3)) // -1复杂度：时间 O(amount × n)，空间 O(amount)
题目 2：单词拆分（LeetCode 139）
给定字符串 s 和字典 wordDict，判断 s 是否可以被拆分为字典中的单词。
解答：
状态定义：dp[i] 表示 s[0..i-1] 是否可以被字典拆分
转移方程：dp[i] = true，若存在 j 使得 dp[j] === true 且 s[j..i-1] 在字典中
s = "leetcode", wordDict = ["leet", "code"]
dp: T F F F T F F F T
0 1 2 3 4 5 6 7 8
dp[4]: dp[0]=true, s[0..3]="leet" ∈ dict → true
dp[8]: dp[4]=true, s[4..7]="code" ∈ dict → true ✓typescript
function wordBreak(s: string, wordDict: string[]): boolean {
const wordSet = new Set(wordDict)
const n = s.length
const dp = new Array(n + 1).fill(false)
dp[0] = true
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true
break
}
}
}
return dp[n]
}
console.log(wordBreak("leetcode", ["leet", "code"])) // true
console.log(wordBreak("applepenapple", ["apple", "pen"])) // true
console.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])) // false复杂度：时间 O(n² × k)（k 为平均字符串比较长度），空间 O(n)
题目 3：最长回文子串（LeetCode 5）
给定字符串 s，找到 s 中最长的回文子串。
解答：
状态定义：dp[i][j] 表示 s[i..j] 是否为回文串
转移方程：
dp[i][j] = (s[i] === s[j]) && (j - i < 3 || dp[i+1][j-1])s = "babad"
b a b a d
b [ T F T F F ]
a [ T F T F ]
b [ T F F ]
a [ T F ]
d [ T ]
最长回文: "bab" 或 "aba" (长度3)typescript
function longestPalindrome(s: string): string {
const n = s.length
const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false))
let start = 0
let maxLen = 1
for (let i = 0; i < n; i++) dp[i][i] = true
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1
if (s[i] === s[j]) {
if (len <= 3) {
dp[i][j] = true
} else {
dp[i][j] = dp[i + 1][j - 1]
}
}
if (dp[i][j] && len > maxLen) {
start = i
maxLen = len
}
}
}
return s.substring(start, start + maxLen)
}
console.log(longestPalindrome("babad")) // "bab"
console.log(longestPalindrome("cbbd")) // "bb"复杂度：时间 O(n²)，空间 O(n²)
题目 4：打家劫舍（LeetCode 198）
小偷沿着一排房屋行窃，相邻的房屋不能同时被偷。求一夜能偷到的最大金额。
解答：
状态定义：dp[i] 表示偷到第 i 间房屋时的最大金额
转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
dp[i-1]：不偷第 i 间dp[i-2] + nums[i]：偷第 i 间（那么第 i-1 间不能偷）
nums = [2, 7, 9, 3, 1]
i: 0 1 2 3 4
dp: 2 7 11 11 12
dp[2] = max(dp[1], dp[0]+9) = max(7, 11) = 11 (偷第0和第2间)
dp[3] = max(dp[2], dp[1]+3) = max(11, 10) = 11 (不偷第3间)
dp[4] = max(dp[3], dp[2]+1) = max(11, 12) = 12 (偷第2和第4间)
最优方案: 偷 [2, 9, 1] = 12typescript
function rob(nums: number[]): number {
if (nums.length === 1) return nums[0]
let prev2 = 0
let prev1 = 0
for (const num of nums) {
const curr = Math.max(prev1, prev2 + num)
prev2 = prev1
prev1 = curr
}
return prev1
}
console.log(rob([2, 7, 9, 3, 1])) // 12
console.log(rob([1, 2, 3, 1])) // 4复杂度：时间 O(n)，空间 O(1)
题目 5：解码方法（LeetCode 91）
给定一个数字字符串 s，每个数字（1-26）可以映射为字母（A-Z）。求解码方法总数。
解答：
状态定义：dp[i] 表示 s[0..i-1] 的解码方法数
转移方程：
若 s[i-1] != '0': dp[i] += dp[i-1] (单独解码 s[i-1])
若 10 <= s[i-2..i-1] <= 26: dp[i] += dp[i-2] (两位一起解码)s = "226"
i=0: dp[0] = 1 (空串)
i=1: s[0]='2' != '0' → dp[1] = dp[0] = 1 解码: "2"→B
i=2: s[1]='2' != '0' → dp[2] = dp[1] = 1 解码: "22"→BB
"22"=22 ∈ [10,26] → dp[2] += dp[0] → dp[2]=2 解码: "22"→V
i=3: s[2]='6' != '0' → dp[3] = dp[2] = 2
"26"=26 ∈ [10,26] → dp[3] += dp[1] → dp[3]=3 解码: BBF, BZ, VF
答案: 3typescript
function numDecodings(s: string): number {
if (s[0] === '0') return 0
const n = s.length
let prev2 = 1
let prev1 = 1
for (let i = 2; i <= n; i++) {
let curr = 0
if (s[i - 1] !== '0') {
curr += prev1
}
const twoDigit = parseInt(s.substring(i - 2, i))
if (twoDigit >= 10 && twoDigit <= 26) {
curr += prev2
}
prev2 = prev1
prev1 = curr
}
return prev1
}
console.log(numDecodings("226")) // 3
console.log(numDecodings("12")) // 2
console.log(numDecodings("06")) // 0复杂度：时间 O(n)，空间 O(1)
十一、追问思考（5 道）
状态压缩 DP 是什么？ 在旅行商问题（TSP）中，如何用位掩码（bitmask）来表示已访问的城市集合？时间复杂度是多少？
为什么 0/1 背包一维优化必须从右往左遍历，而完全背包从左往右？ 如果遍历方向搞反会出现什么结果？请举一个具体的反例说明。
编辑距离能否用空间 O(min(m, n)) 实现？ 如果还需要回溯出具体的编辑操作序列，空间复杂度最优能达到多少？（提示：Hirschberg 算法）
最长递增子序列（LIS）的 O(n log n) 解法中，
tails数组存的并不是真正的 LIS。 如何在 O(n log n) 时间内不仅求出 LIS 的长度，还恢复出一个具体的 LIS 序列？动态规划和强化学习有什么联系？ 贝尔曼方程（Bellman Equation）在两个领域中分别扮演什么角色？状态、动作、奖励、值函数之间如何类比？