动态规划
本章目标：掌握 DP 五步法，能独立完成一维、二维、区间、状态压缩等各类 DP 题。
你将学到
- DP 五步法：状态定义 → 转移方程 → 初始条件 → 计算顺序 → 答案位置
- 一维 DP（爬楼梯、LIS、最大子数组）
- 二维 DP（背包、编辑距离、LCS、不同路径）
- 区间 DP（回文子串、戳气球）
- 状态压缩（位运算 DP）
- 记忆化搜索 vs 自底向上
1. 概念
动态规划是面试中最重要的算法，核心思想是将问题分解为重叠子问题，避免重复计算。与分治不同，DP 的子问题有大量重叠。
DP 适用的两个条件：
- 最优子结构：原问题的最优解包含子问题的最优解
- 重叠子问题：不同的递归路径会反复求解同一个子问题
DP 五步法
- 定义状态：
dp[i]或dp[i][j]代表什么？ - 写出转移方程：
dp[i]由哪些子状态推出？ - 初始条件：
dp[0]或dp[0][0]是多少？ - 计算顺序：从小到大还是从大到小？拓扑序保证依赖已计算。
- 答案位置：最终结果在
dp[n]还是dp数组中的最大值？
2. 核心模板
一维 DP：最长递增子序列 LIS
python
def lengthOfLIS(nums):
"""O(n²) DP 解法"""
if not nums:
return 0
n = len(nums)
dp = [1] * n # dp[i] = 以 nums[i] 结尾的最长递增子序列长度
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)LIS 的 O(n log n) 优化（贪心 + 二分）：
python
from bisect import bisect_left
def lengthOfLIS_optimized(nums):
tails = [] # tails[i] = 长度为 i+1 的递增子序列的最小尾元素
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)二维 DP：编辑距离
python
def minDistance(word1, word2):
"""将 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 # 删除 i 个字符
for j in range(n + 1):
dp[0][j] = 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] = 1 + min(
dp[i-1][j], # 删除
dp[i][j-1], # 插入
dp[i-1][j-1] # 替换
)
return dp[m][n]复杂度
- 一维 DP：时间 O(n) 或 O(n²)，空间 O(n)
- 二维 DP：时间 O(mn)，空间 O(mn) 或 O(n)（滚动数组优化）
3. 经典题目精讲
LeetCode 70 · 爬楼梯
题意：每次爬 1 或 2 级台阶，有多少种方法爬到第 n 级？
思路：dp[i] = dp[i-1] + dp[i-2]，本质就是斐波那契。
python
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return currLeetCode 322 · 零钱兑换
题意：给定硬币面额和金额，求凑成金额所需最少硬币数。
思路：完全背包 DP。dp[i] = 金额 i 所需最少硬币数。
python
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1LeetCode 416 · 分割等和子集
题意：判断数组能否分成两个子集使它们的和相等。
思路：转化为 0-1 背包——能否选若干元素之和等于 sum/2。
python
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1): # 逆序！
dp[j] = dp[j] or dp[j - num]
return dp[target]LeetCode 1143 · 最长公共子序列
题意：找两个字符串的最长公共子序列长度。
python
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]4. 易错点
- ⚠️ 0-1 背包内层循环必须逆序，完全背包正序
- ⚠️ dp 数组初始化时
dp[0]的含义要仔细确认 - ⚠️ 滚动数组优化时只保留上一行/列，注意覆盖顺序
- ⚠️ 记忆化搜索用
@lru_cache时注意参数必须可哈希
5. 推荐刷题清单
| 题号 | 题名 | 难度 | 关键 |
|---|---|---|---|
| 5 | 最长回文子串 | Medium | 区间 DP |
| 53 | 最大子数组和 | Medium | 一维 DP |
| 70 | 爬楼梯 | Easy | 斐波那契 |
| 72 | 编辑距离 | Medium | 二维 DP |
| 152 | 乘积最大子数组 | Medium | 一维 DP |
| 198 | 打家劫舍 | Medium | 状态机 DP |
| 300 | 最长递增子序列 | Medium | LIS |
| 322 | 零钱兑换 | Medium | 完全背包 |
| 416 | 分割等和子集 | Medium | 0-1 背包 |
| 1143 | 最长公共子序列 | Medium | 二维 DP |
延伸阅读
- LeetCode 官方
- 代码随想录
- 《算法导论》(CLRS) 第 15 章