动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题的解以避免重复计算的高效算法思想。其核心在于“最优子结构”（问题的最优解包含其子问题的最优解）和“重叠子问题”（递归算法会反复求解相同的子问题）[ref_1][ref_3]。Python凭借其清晰的语法和丰富的数据结构（如列表、字典），非常适合实现动态规划算法。 ## 一、动态规划核心要素与Python实现范式 动态规划的实现通常围绕三个核心要素：**状态定义**、**状态转移方程**和**边界条件**[ref_1][ref_3]。Python实现主要有两种范式：**自顶向下的备忘录法**和**自底向上的迭代法**。 ### 1. 自顶向下备忘录法（递归+缓存） 这种方法从原问题出发，递归地分解为子问题，并使用缓存（如字典）存储已计算的子问题结果。 ```python def fib_memo(n, memo=None): """ 使用备忘录法计算斐波那契数列第n项[ref_6]。 状态定义：f(i) 表示斐波那契数列第i项的值。 状态转移：f(i) = f(i-1) + f(i-2)。 边界条件：f(0)=0, f(1)=1。 """ if memo is None: memo = {} # 初始化缓存字典 if n in memo: return memo[n] # 已计算，直接返回 if n <= 1: result = n else: # 递归计算并缓存结果 result = fib_memo(n-1, memo) + fib_memo(n-2, memo) memo[n] = result return result # 测试 print(fib_memo(10)) # 输出：55 ``` ### 2. 自底向上迭代法（递推） 这种方法从最小的子问题开始，逐步迭代构建出原问题的解，通常使用数组（列表）来存储状态。 ```python def fib_dp(n): """ 使用自底向上动态规划计算斐波那契数列[ref_6]。 """ if n <= 1: return n # dp数组，dp[i]表示斐波那契数列第i项的值 dp = [0] * (n + 1) # 初始化边界条件 dp[0], dp[1] = 0, 1 # 状态转移：从已知的小问题递推到大问题 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] # 测试 print(fib_dp(10)) # 输出：55 ``` **两种方法对比**： | 特性 | 自顶向下备忘录法 | 自底向上迭代法 | | :--- | :--- | :--- | | **思路** | 递归分解，遇到子问题先查表 | 从基础情况开始，逐步递推 | | **实现** | 通常用递归 + 字典/列表缓存 | 通常用循环 + 数组（列表） | | **优点** | 思路直观，只计算必要的子问题 | 无递归开销，空间有时可优化 | | **缺点** | 递归有深度限制和函数调用开销 | 可能需要计算所有子问题 | | **Python适用场景** | 子问题空间不规则或稀疏时 | 子问题顺序明确且需要最优性能时 | ## 二、经典问题Python实现详解 ### 1. 爬楼梯问题（类似斐波那契） **问题**：每次可以爬1或2个台阶，到第n阶有多少种方法？ ```python def climb_stairs(n): """ 爬楼梯问题动态规划解法[ref_3]。 状态定义：dp[i]表示到达第i阶台阶的方法数。 状态转移：dp[i] = dp[i-1] + dp[i-2] (从i-1阶爬1步，或从i-2阶爬2步)。 边界条件：dp[0]=1, dp[1]=1。 """ if n <= 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] # 空间优化版：只保留前两个状态 def climb_stairs_opt(n): if n <= 1: return 1 prev, curr = 1, 1 # 代表dp[0]和dp[1] for i in range(2, n + 1): prev, curr = curr, prev + curr return curr print(climb_stairs(5)) # 输出：8 print(climb_stairs_opt(5)) # 输出：8 ``` ### 2. 背包问题（0-1背包） **问题**：给定物品重量`weights`和价值`values`，背包容量`capacity`，求最大价值。 ```python def knapsack_01(weights, values, capacity): """ 0-1背包问题动态规划解法[ref_1]。 状态定义：dp[i][w]表示考虑前i个物品，在容量w下的最大价值。 状态转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]) (如果第i个物品能放下)。 边界条件：dp[0][...] = 0。 """ n = len(weights) # 初始化dp表，(n+1)行，(capacity+1)列 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, capacity + 1): # 当前物品索引是i-1 if weights[i-1] <= w: # 选择：不放当前物品 或 放当前物品 dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) else: # 放不下，只能继承之前的状态 dp[i][w] = dp[i-1][w] return dp[n][capacity] # 空间优化：使用一维数组，逆序更新 def knapsack_01_opt(weights, values, capacity): dp = [0] * (capacity + 1) for i in range(len(weights)): # 必须逆序更新，确保每个物品只被计算一次 for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity] weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 8 print(knapsack_01(weights, values, capacity)) # 输出：10 (选择物品2和4) print(knapsack_01_opt(weights, values, capacity)) # 输出：10 ``` ### 3. 最长公共子序列（LCS） **问题**：给定两个字符串，求它们的最长公共子序列的长度。 ```python def longest_common_subsequence(text1, text2): """ 最长公共子序列(LCS)动态规划解法[ref_1]。 状态定义：dp[i][j]表示text1[0:i]和text2[0:j]的LCS长度。 状态转移： 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]) 边界条件：dp[0][j] = 0, dp[i][0] = 0。 """ 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] text1 = "abcde" text2 = "ace" print(longest_common_subsequence(text1, text2)) # 输出：3 ("ace") ``` ### 4. 找零钱问题（完全背包） **问题**：给定不同面额的硬币`coins`，求凑成总金额`amount`所需的最少硬币数。 ```python def coin_change(coins, amount): """ 找零钱问题（硬币最小数量）动态规划解法[ref_5]。 状态定义：dp[i]表示凑成金额i所需的最少硬币数。 状态转移：dp[i] = min(dp[i], dp[i - coin] + 1) for coin in coins if i >= coin。 边界条件：dp[0] = 0，其他初始化为一个极大值（如amount+1）。 """ # 初始化dp数组，dp[i] = amount+1 表示不可达（因为最多用amount个1元硬币） dp = [amount + 1] * (amount + 1) dp[0] = 0 # 金额为0时不需要硬币 # 遍历所有金额 for i in range(1, amount + 1): # 尝试每一种硬币 for coin in coins: if i >= coin: dp[i] = min(dp[i], dp[i - coin] + 1) # 如果dp[amount]未被更新，说明无法凑出 return dp[amount] if dp[amount] <= amount else -1 coins = [1, 2, 5] amount = 11 print(coin_change(coins, amount)) # 输出：3 (5+5+1) ``` ### 5. 摆动序列问题 **问题**：计算长度为 n 的摆动序列的个数。摆动序列是指连续数字之间的差严格地在正数和负数之间交替[ref_2]。 ```python def wiggle_max_length(nums): """ 摆动序列问题动态规划解法[ref_2]。 状态定义： up[i]: 以nums[i]结尾，并且最后是上升趋势的最长摆动序列长度。 down[i]: 以nums[i]结尾，并且最后是下降趋势的最长摆动序列长度。 状态转移： if nums[i] > nums[j]: up[i] = max(up[i], down[j] + 1) if nums[i] < nums[j]: down[i] = max(down[i], up[j] + 1) """ if not nums: return 0 n = len(nums) up, down = [1] * n, [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: up[i] = max(up[i], down[j] + 1) elif nums[i] < nums[j]: down[i] = max(down[i], up[j] + 1) return max(up[-1], down[-1]) nums = [1, 7, 4, 9, 2, 5] print(wiggle_max_length(nums)) # 输出：6 (整个序列就是摆动序列) ``` ## 三、动态规划解题通用步骤与Python技巧 1. **定义状态**：明确`dp`数组（或字典）以及下标的含义。例如，`dp[i]`、`dp[i][j]`分别代表什么。 2. **确定状态转移方程**：找出如何从已知状态推导出未知状态，这是动态规划的核心[ref_1][ref_3]。 3. **初始化边界条件**：给最小的、不可再分的子问题赋值。 4. **确定遍历顺序**：确保在计算当前状态时，其所依赖的子状态已经被计算过。 5. **输出结果**：`dp`数组的哪个状态是最终答案。 **Python实现中的常见优化技巧**： * **空间优化**：如果当前状态只与有限的几个历史状态有关，可以使用滚动数组或变量替换完整的`dp`表。例如在斐波那契和爬楼梯问题中，只需两个变量[ref_6]。 * **使用字典备忘录**：当状态不是连续的整数索引时（例如在字符串或树形DP中），使用字典`dict`作为备忘录比列表更灵活。 * **使用`@lru_cache`装饰器**：Python的`functools.lru_cache`可以轻松实现自顶向下的备忘录，无需手动管理缓存。 ```python from functools import lru_cache @lru_cache(maxsize=None) def fib_lru(n): if n <= 1: return n return fib_lru(n-1) + fib_lru(n-2) ``` 动态规划是解决最优化和计数问题的强大工具。掌握状态定义和转移方程的寻找是关键，而Python的简洁语法和强大数据结构能让你更专注于算法逻辑本身[ref_1][ref_5]。从经典的背包、LCS问题入手，逐步扩展到更复杂的问题，是学习动态规划的有效路径。