动态规划：状态定义、转移方程与空间优化
动态规划（Dynamic Programming, DP）是算法面试中最具区分度的题型。掌握 DP 的核心方法论，能让你在面试中脱颖而出。
一、DP 核心思维
从递归到 DP 的三步转换
- 定义状态：
dp[i]或dp[i][j]代表什么？ - 状态转移：如何从已知推导出未知？
- 初始条件与边界：起点是什么？终点是什么？
示例：爬楼梯（LeetCode 70）
问题：n 阶楼梯，每次爬 1 或 2 阶，有多少种方法？
递归思路：f(n) = f(n-1) + f(n-2)
↓ 展开有重叠子问题
↓ 用数组缓存结果
DP：dp[i] = dp[i-1] + dp[i-2]
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 空间优化：只需要前两个值
def climb_stairs_optimized(n):
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
二、经典 DP 模型
1. 线性 DP
打家劫舍（LeetCode 198）：不相邻房屋的最大金额
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, prev2 + nums[i])
prev2, prev1 = prev1, curr
return prev1
状态定义：dp[i] = 前 i 个房屋能偷的最大金额
转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
2. 股票问题系列
股票买卖（LeetCode 121）：只能买卖一次
def max_profit(prices):
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
股票买卖 II（LeetCode 122）：可以买卖多次
def max_profit_ii(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
股票买卖 III（LeetCode 123）：最多买卖两次
def max_profit_iii(prices):
if not prices:
return 0
buy1 = buy2 = float('-inf')
sell1 = sell2 = 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2
3. 背包问题
01 背包：每个物品只能选一次
def knapsack_01(weights, values, capacity):
n = len(weights)
# dp[j] = 容量为 j 时的最大价值
dp = [0] * (capacity + 1)
for i in range(n):
# 倒序遍历，防止重复选择
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
完全背包：每个物品可以选无限次
def knapsack_unbounded(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# 正序遍历，允许重复选择
for j in range(weights[i], capacity + 1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
4. 区间 DP
最长回文子序列（LeetCode 516）
def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
5. 编辑距离（LeetCode 72）
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1]) + 1 # 替换
return dp[m][n]
三、空间优化技巧
1. 滚动数组
当 dp[i] 只依赖于前一行/前几行时，可以压缩维度。
# 二维 DP 压缩为一维（如 01 背包）
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
2. 状态压缩 DP
当状态可以用二进制表示时（如旅行商问题、集合选择）。
# 示例：状态压缩 DP 框架
dp = [[0] * (1 << n) for _ in range(n)]
for mask in range(1 << n):
for i in range(n):
if not (mask & (1 << i)):
continue
for j in range(n):
if mask & (1 << j):
continue
dp[j][mask | (1 << j)] = min(dp[j][mask | (1 << j)],
dp[i][mask] + cost[i][j])
四、DP 思维框架
解题步骤
判断是否为 DP 问题
- 最优子结构？（问题的最优解包含子问题的最优解）
- 重叠子问题？（递归解法有大量重复计算）
定义状态
- 一维还是二维？
- 状态的具体含义是什么？
推导转移方程
- 最后一步做了什么选择？
- 从前面的哪些状态转移过来？
确定边界条件
- dp[0]、dp[1] 等初始值
确定遍历顺序
- 外层循环是什么？内层循环是什么？
- 正向还是反向？
空间优化（可选）
- 能否滚动数组？
- 能否状态压缩？
五、经典面试题
| 题号 | 题目 | 模型 | 难度 |
|---|---|---|---|
| LeetCode 70 | 爬楼梯 | 线性 DP | Easy |
| LeetCode 198 | 打家劫舍 | 线性 DP | Medium |
| LeetCode 121 | 买卖股票的最佳时机 | 线性 DP | Easy |
| LeetCode 122 | 买卖股票的最佳时机 II | 贪心/DP | Medium |
| LeetCode 123 | 买卖股票的最佳时机 III | 状态机 DP | Hard |
| LeetCode 416 | 分割等和子集 | 01 背包 | Medium |
| LeetCode 518 | 零钱兑换 II | 完全背包 | Medium |
| LeetCode 516 | 最长回文子序列 | 区间 DP | Medium |
| LeetCode 72 | 编辑距离 | 二维 DP | Hard |
| LeetCode 10 | 正则表达式匹配 | 二维 DP | Hard |
| LeetCode 32 | 最长有效括号 | 线性 DP | Hard |
六、面试常见问题
Q: DP 和贪心的区别？
- DP：每个状态都考虑子问题的最优解，保证全局最优
- 贪心：每一步做局部最优选择，不保证全局最优
- 能用贪心的问题一定具有「贪心选择性质」，比 DP 条件更强
Q: 自顶向下（记忆化搜索）vs 自底向上（递推）怎么选？
- 记忆化搜索：代码更直观，适合状态转移复杂的情况
- 递推：常数更小，适合状态转移规律清晰的情况
- 面试建议：先写记忆化搜索确保正确，再改为递推优化
Q: 如何判断 DP 的状态定义是否正确？
- 能否覆盖所有可能的情况？
- 状态之间是否有重叠？
- 转移方程是否无后效性？（当前决策只依赖之前状态）
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。