从零开始的数据结构教程（五）​​动态规划（DP）

---

🧩 标题一：DP 核心思想——拼乐高式的解题法

动态规划（DP）是一种强大的算法设计范式，它通过将一个复杂问题拆解成更小的子问题，并存储这些子问题的解来避免重复计算，从而高效地解决问题。想象你正在拼一套大型乐高，你不会每次都从头开始寻找每个零件，而是会把已经拼好的小模块放在一边，需要时直接取用。

三大特征

要判断一个问题是否适合用 DP 解决，通常需要满足以下三个特征：

1. 重叠子问题：解决大问题需要多次计算相同的子问题。最经典的例子就是斐波那契数列，计算 fib(5) 需要多次计算 fib(3) 等。
2. 最优子结构：一个问题的全局最优解可以通过局部最优解组合得到。例如，最短路径问题中，最短路径上的任意子路径也必须是最短的。
3. 无后效性：当前阶段的决策只依赖于之前的状态，而不影响未来决策的制定，也不会影响已做出的过去决策。比如股票买卖中，你今天的盈亏只取决于今天的操作和之前的持有状态，与你未来如何操作无关。

自顶向下 vs 自底向上

DP 通常有两种实现方式：

方法	实现方式	适用场景
递归 + 备忘录	从目标问题分解，递归解决子问题，并将结果存储起来（记忆化搜索）。	问题边界清晰，适合直接将数学公式转化为代码时。
迭代填表	从基础 case 逐步推导，通过循环迭代填充 DP 表，直至得到最终解。	需要优化空间复杂度时，或者对问题状态推导过程有清晰认知时。

# 斐波那契数列的 DP 解法对比# 自顶向下（递归 + 备忘录）
def fib_memo(n, memo={0:0, 1:1}):if n not in memo:memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)return memo[n]# 自底向上（迭代填表，空间优化版）
def fib_table(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):# 每次迭代，a 变成前一个 b 的值，b 变成 a 和 b 的和（即新的斐波那契数）a, b = b, a + breturn b# 测试
# print(fib_memo(10))  # 输出 55
# print(fib_table(10)) # 输出 55

---

💰 标题二：经典问题——股票买卖的最佳时机

这类问题是 DP 的入门级考题，通常会问你在给定股价历史数据中，如何实现最大利润。

问题变体

1. 最多 1 次交易（LeetCode 121）：

   • 思想：你只能买卖一次，那么最佳策略就是在价格最低点买入，在价格最高点卖出（且卖出日期在买入日期之后）。
   • DP 状态：维护历史最低价 min_price 和当前最大利润 max_profit。

   def maxProfit(prices):min_price = float('inf') # 记录历史最低买入价max_profit = 0           # 记录能获得的最大利润for price in prices:min_price = min(min_price, price)       # 更新最低买入价max_profit = max(max_profit, price - min_price) # 计算当前卖出能获得的最大利润return max_profit
   

2. 无限次交易（LeetCode 122）：

   • 思想：如果你可以无限次交易，那么只要今天比昨天价格高，你就卖出获利。这是一种贪心思想，每次赚取小利润，累加起来就是总利润。
   • DP 状态：不需要复杂的状态，直接累加所有上涨的差价。

   def maxProfit_unlimited(prices):profit = 0for i in range(1, len(prices)):if prices[i] > prices[i-1]: # 只要今天比昨天高，就进行一次买卖profit += prices[i] - prices[i-1]return profit
   

3. 含冷冻期（LeetCode 309）：

   • 思想：引入“冷却期”后，问题变得复杂。你需要用多个状态来表示在每一天结束时你可能处于的不同情况（例如：持有股票、不持有股票且处于冷冻期、不持有股票且非冷冻期）。
   • DP 状态：dp[i][0] 表示第 i 天结束后手里没有股票，且当天没有卖出；dp[i][1] 表示第 i 天结束后手里持有股票；dp[i][2] 表示第 i 天结束后手里没有股票，且当天是卖出股票后的冷冻期第一天。通过状态转移方程在这些状态之间进行推导。

---

🎒 标题三：背包问题——旅行装箱的终极优化

背包问题是一类经典的优化问题，通常要求你在容量限制下选择物品以最大化总价值。

0-1 背包模板

• 问题：你有一个容量为 W 的背包，以及 N 件物品。每件物品有自己的重量 w[i] 和价值 v[i]，并且每件物品只能选择 0 次或 1 次。目标是最大化背包中物品的总价值。

def knapsack(W, weights, values):n = len(weights)# dp[i][j] 表示：考虑前 i 件物品，背包容量为 j 时的最大价值dp = [[0] * (W + 1) for _ in range(n + 1)]# 填充 DP 表for i in range(1, n + 1):  # 遍历物品，从第1件到第n件for j in range(1, W + 1):  # 遍历背包容量，从1到W# 当前物品的重量是 weights[i-1]（因为物品索引从0开始）# 当前物品的价值是 values[i-1]if weights[i-1] <= j: # 如果当前物品能放入背包# 两种选择：# 1. 不放当前物品：价值是 dp[i-1][j]# 2. 放入当前物品：价值是 values[i-1] + dp[i-1][j - weights[i-1]]#    (j - weights[i-1] 是放入当前物品后，剩余的背包容量)dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j - weights[i-1]])else: # 当前物品太重，无法放入背包dp[i][j] = dp[i-1][j] # 只能选择不放当前物品return dp[n][W] # 最终结果在 dp[n][W]

空间优化

0-1 背包问题可以通过一维数组进行空间优化，将空间复杂度从 $O(nW)$ 降到 $O(W)$。关键在于倒序更新容量 j，以确保在计算 dp[j] 时，dp[j - weights[i]] 仍然是上一轮（即 dp[i-1]）的值，而不是本轮（dp[i]）已经更新过的值。

def knapsack_optimized(W, weights, values):n = len(weights)dp = [0] * (W + 1) # dp[j] 表示当前容量 j 下的最大价值for i in range(n): # 遍历物品# 倒序遍历容量，确保每个物品只被考虑一次（0-1 背包特性）for j in range(W, weights[i] - 1, -1):dp[j] = max(dp[j], values[i] + dp[j - weights[i]])return dp[W]

---

🔍 标题四：高频面试题——最长公共子序列（LCS）

场景

最长公共子序列（LCS）问题常用于比较两个序列的相似度，例如DNA 序列比对、文件差异比较 (diff 命令)。它不要求子序列在原序列中是连续的。

def longestCommonSubsequence(text1, text2):m, n = len(text1), len(text2)# dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1): # 遍历 text1for j in range(1, n + 1): # 遍历 text2if text1[i-1] == text2[j-1]: # 如果当前字符匹配# LCS 长度是前一个字符的 LCS 长度 + 1dp[i][j] = dp[i-1][j-1] + 1else: # 如果当前字符不匹配# LCS 长度是 (text1 减少一个字符) 和 (text2 减少一个字符) 两种情况的最大值dp[i][j] = max(dp[i-1][j], dp[i][j-1])return dp[m][n] # 最终结果在 dp[m][n]

状态转移方程

• 当 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 问题分类

DP 问题种类繁多，但通常可以归纳为几大类：

问题类型	典型例题	状态定义技巧
线性 DP	最大子数组和（LeetCode 53）	dp[i] 表示以第 i 个元素结尾的最优解。
区间 DP	戳气球（LeetCode 312）	dp[i][j] 表示区间 i 到 j 的最优解。
状态机 DP	打家劫舍（LeetCode 198）、股票买卖系列	用多个状态（如 dp[i][持有]、dp[i][不持有]）表示选择或不选择某种行为。
背包 DP	0-1 背包、完全背包	dp[i][j] 表示考虑前 i 件物品，容量为 j 的最优解。
序列型 DP	最长公共子序列、编辑距离	dp[i][j] 表示前 i 个和前 j 个元素的最优解。

---