一、动态规划的核心思想
动态规划（DP）就像我们生活中做决策的过程。假设你要从家到公司，中间有多个换乘站，你会先考虑"到前一站的最优路径"，再逐步推导到终点的最优解。这就是DP的核心——将大问题拆解为相互关联的子问题。
动态规划有三个关键特征：
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：不同的决策序列会到达相同的子问题
- 无后效性：未来的决策只依赖于当前状态，不依赖于如何到达当前状态
举个生活中的例子：爬楼梯问题。假设每次可以爬1或2个台阶，问到第n阶有多少种方法？这个问题就完美符合DP的三个特征。
二、状态转移方程的推导方法
状态转移方程是动态规划的灵魂，就像做菜时的食谱。下面介绍三种推导方法：
2.1 从暴力递归到记忆化搜索
先看斐波那契数列的例子（技术栈：Python）：
# 暴力递归解法 - 时间复杂度O(2^n)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# 记忆化搜索 - 时间复杂度O(n)
memo = [0]*(n+1)
def fib_memo(n):
if n <= 1:
return n
if memo[n] != 0:
return memo[n]
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
这个演变过程展示了如何通过添加"备忘录"来优化重复计算。
2.2 自底向上的递推方法
还是斐波那契的例子，现在我们用迭代的方式：
# 动态规划解法 - 时间复杂度O(n)，空间复杂度O(n)
def fib_dp(n):
if n <= 1:
return n
dp = [0]*(n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空间优化版 - 空间复杂度O(1)
def fib_dp_opt(n):
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n+1):
prev, curr = curr, prev + curr
return curr
2.3 经典问题示例：零钱兑换
给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币数（技术栈：Python）：
def coinChange(coins, amount):
# dp[i]表示凑成金额i所需的最少硬币数
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 金额0需要0个硬币
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# 示例
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount)) # 输出3 (5+5+1)
这个例子展示了如何定义状态（dp数组）和状态转移方程（dp[i] = min(dp[i], dp[i-coin]+1)）。
三、模板化解题思路
经过大量刷题后，我总结出了一套动态规划的解题模板：
3.1 四步解题法
- 定义状态：明确dp数组的含义
- 确定初始条件：设置边界条件
- 推导状态转移方程：找出递推关系
- 确定计算顺序：自顶向下还是自底向上
3.2 经典模板应用：最长递增子序列
给定一个整数数组，找到其中最长严格递增子序列的长度（技术栈：Python）：
def lengthOfLIS(nums):
if not nums:
return 0
# dp[i]表示以nums[i]结尾的最长递增子序列长度
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 示例
nums = [10,9,2,5,3,7,101,18]
print(lengthOfLIS(nums)) # 输出4 (2,3,7,101)
3.3 背包问题模板
0-1背包问题是动态规划的经典问题。模板如下：
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][j]表示前i个物品，背包容量为j时的最大价值
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for j in range(1, capacity+1):
if j >= w:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity]
# 示例
weights = [2,3,4,5]
values = [3,4,5,6]
capacity = 8
print(knapsack(weights, values, capacity)) # 输出10 (物品2和4)
四、高级技巧与优化策略
4.1 状态压缩
当状态转移只依赖于有限的几个前驱状态时，可以进行空间优化。比如斐波那契数列的空间优化，以及背包问题的滚动数组优化：
# 0-1背包空间优化版
def knapsack_opt(weights, values, capacity):
n = len(weights)
dp = [0]*(capacity+1)
for i in range(n):
w, v = weights[i], values[i]
# 需要逆向遍历，避免重复计算
for j in range(capacity, w-1, -1):
dp[j] = max(dp[j], dp[j-w] + v)
return dp[capacity]
4.2 多维状态处理
有些问题需要定义多维状态。比如股票买卖问题：
def maxProfit(prices):
if not prices:
return 0
# dp[i][0]表示第i天持有股票时的最大利润
# dp[i][1]表示第i天不持有股票时的最大利润
dp = [[0]*2 for _ in range(len(prices))]
dp[0][0] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][0], -prices[i]) # 只能买一次
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
return dp[-1][1]
# 示例
prices = [7,1,5,3,6,4]
print(maxProfit(prices)) # 输出5 (第2天买，第5天卖)
4.3 区间DP问题
区间DP通常用于解决涉及区间操作的问题，比如矩阵链乘法、回文子串等：
# 最长回文子序列
def longestPalindromeSubseq(s):
n = len(s)
# dp[i][j]表示s[i..j]的最长回文子序列长度
dp = [[0]*n for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][i] = 1 # 单个字符的回文长度为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]
# 示例
s = "bbbab"
print(longestPalindromeSubseq(s)) # 输出4 (bbbb)
五、应用场景与技术总结
动态规划广泛应用于：
- 最优化问题：最短路径、最大价值等
- 组合计数问题：多少种方式/方法
- 决策问题：游戏策略、资源分配
技术优缺点： 优点：
- 能够高效解决具有重叠子问题特性的复杂问题
- 通过记忆化避免重复计算
- 代码通常简洁优雅
缺点：
- 需要找到正确的状态定义和转移方程
- 可能面临"维度诅咒"（高维状态空间）
- 有些问题难以识别是否适用DP
注意事项：
- 先尝试用递归思路思考问题，再转化为DP
- 注意边界条件的处理
- 合理选择自顶向下（记忆化）或自底向上（递推）
- 考虑空间优化可能性
总结来说，掌握动态规划需要大量练习，培养对状态的敏感度。建议从经典问题入手，逐步建立解题直觉。记住，DP不是死记硬背模板，而是理解问题分解的思想。当你遇到新问题时，尝试将其分解为子问题，定义合适的状态，推导转移关系，这就是动态规划的精髓所在。
评论