动态规划 (Dynamic Programming)
动态规划 (Dynamic Programming)
动态规划是一种通过将复杂问题分解为子问题,并存储子问题的解来避免重复计算的算法设计方法。
基础概念
核心要素
- 最优子结构:问题的最优解包含子问题的最优解
- 重叠子问题:同一个子问题在递归过程中被重复计算
- 状态转移:从已知状态推导新状态的过程
常见类型
- 线性DP:状态与前几个状态有关
dp[i] = f(dp[i-1], dp[i-2], ...)
- 区间DP:状态与区间两端有关
dp[i][j] = f(dp[i+1][j], dp[i][j-1], ...)
- 背包DP:状态与容量和选择有关
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
解题步骤
- 定义状态:明确dp数组含义
- 状态转移:写出状态转移方程
- 初始化:设置初始状态
- 遍历顺序:确定计算顺序
- 返回结果:获取最终答案
经典问题
1. 爬楼梯(线性DP)
状态转移过程:
n = 5的所有可能:
1,1,1,1,1
1,1,1,2
1,1,2,1
1,2,1,1
2,1,1,1
1,2,2
2,1,2
2,2,1
dp[i] = dp[i-1] + dp[i-2]
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
dp[5] = 8
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
2. 零钱兑换(完全背包)
状态转移过程:
coins = [1,2,5], amount = 11
dp[i]: 凑成金额i所需的最少硬币数
dp[0] = 0
dp[1] = 1 (1)
dp[2] = 1 (2)
dp[3] = 2 (1+2)
dp[4] = 2 (2+2)
dp[5] = 1 (5)
dp[6] = 2 (5+1)
...
dp[11] = 3 (5+5+1)
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
3. 最长回文子串(区间DP)
LeetCode 5 - Longest Palindromic Substring
状态转移过程:
s = "babad"
dp[i][j]: s[i:j+1]是否为回文串
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"
def longestPalindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_len = 0, 1
# 单个字符都是回文
for i in range(n):
dp[i][i] = True
# 检查长度为2及以上的子串
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if length == 2:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
if dp[i][j] and length > max_len:
start = i
max_len = length
return s[start:start + max_len]
4. 编辑距离(双序列DP)
状态转移过程:
word1 = "horse", word2 = "ros"
dp[i][j]: word1前i个字符转换到word2前j个字符需要的最少操作数
∅ 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
操作过程:
1. horse -> rorse (替换'h'为'r')
2. rorse -> rose (删除'r')
3. rose -> ros (删除'e')
def minDistance(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
# 填充dp表
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] + 1, # 删除
dp[i][j-1] + 1, # 插入
dp[i-1][j-1] + 1 # 替换
)
return dp[m][n]
常见DP类型
1. 线性DP
- 斐波那契数列
- 最大子数组和
- 打家劫舍
2. 区间DP
- 最长回文子串
- 戳气球
- 矩阵链乘法
3. 背包问题
- 0-1背包
- 完全背包
- 多重背包
4. 状态压缩DP
- 旅行商问题
- 集合覆盖
- 状态游戏
5. 树形DP
- 树的最大独立集
- 树的最小支配集
- 树的最小顶点覆盖
优化技巧
- 状态压缩:使用位运算表示状态
- 空间优化:使用滚动数组
- 记忆化搜索:自顶向下的DP
- 单调队列/栈优化
- 斜率优化