摘要动态规划（Dynamic Programming，DP）是算法设计中的一种重要思想，广泛应用于各类优化问题。本文将深入讲解动态规划的基本概念、核心要素、解题步骤和经典问题。我们将通过背包问题、爬楼梯问题、编辑距离等经典案例，详细介绍动态规划的思维过程和实现方法。文章包含丰富的图示和Python代码示例，帮助读者掌握动态规划的精髓，提升算法设计和问题解决能力。
正文1. 引言动态规划是解决具有重叠子问题和最优子结构性质问题的一种算法设计技术。它将复杂问题分解为更小的子问题，通过保存子问题的解来避免重复计算，从而提高算法效率。动态规划广泛应用于最优化问题，如资源分配、路径规划、序列比对等领域。
2. 动态规划基本概念2.1 核心要素动态规划问题通常具有以下三个核心要素：
重叠子问题：问题可以分解为相互重叠的子问题最优子结构：问题的最优解包含子问题的最优解无后效性：某阶段状态一旦确定，不受这个状态以后决策的影响2.2 解题步骤使用动态规划解决问题通常包括以下步骤：
定义状态：确定用哪些变量表示问题的状态状态转移方程：找出状态之间的递推关系初始化：确定初始状态的值计算顺序：确定状态的计算顺序返回结果：根据计算结果返回最终答案3. 经典动态规划问题3.1 0-1背包问题0-1背包问题是动态规划的经典问题之一。给定一个容量为cap的背包和n个物品，每个物品有重量wgt[i]和价值val[i]，要求在不超过背包容量的前提下，使装入背包的物品总价值最大。
暴力搜索解法
def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
"""0-1 背包：暴力搜索"""
# 若已选完所有物品或背包无剩余容量，则返回价值 0
if i == 0 or c == 0:
return 0
# 若超过背包容量，则只能选择不放入背包
if wgt[i - 1] > c:
return knapsack_dfs(wgt, val, i - 1, c)
# 计算不放入和放入物品 i 的最大价值
no = knapsack_dfs(wgt, val, i - 1, c)
yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
# 返回两种方案中价值更大的那一个
return max(no, yes)
记忆化搜索优化
def knapsack_dfs_mem(
wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int
) -> int:
"""0-1 背包：记忆化搜索"""
# 若已选完所有物品或背包无剩余容量，则返回价值 0
if i == 0 or c == 0:
return 0
# 若已有记录，则直接返回
if mem[i][c] != -1:
return mem[i][c]
# 若超过背包容量，则只能选择不放入背包
if wgt[i - 1] > c:
return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
# 计算不放入和放入物品 i 的最大价值
no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
# 记录并返回两种方案中价值更大的那一个
mem[i][c] = max(no, yes)
return mem[i][c]
动态规划解法
def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
"""0-1 背包：动态规划"""
n = len(wgt)
# 初始化 dp 表
dp = [[0] * (cap + 1) for _ in range(n + 1)]
# 状态转移
for i in range(1, n + 1):
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# 若超过背包容量，则不选物品 i
dp[i][c] = dp[i - 1][c]
else:
# 不选和选物品 i 这两种方案的较大值
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
return dp[n][cap]
def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
"""0-1 背包：空间优化后的动态规划"""
n = len(wgt)
# 初始化 dp 表
dp = [0] * (cap + 1)
# 状态转移
for i in range(1, n + 1):
# 倒序遍历
for c in range(cap, 0, -1):
if wgt[i - 1] > c:
# 若超过背包容量，则不选物品 i
dp[c] = dp[c]
else:
# 不选和选物品 i 这两种方案的较大值
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap]
3.2 爬楼梯问题爬楼梯问题是另一个经典的动态规划问题。假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶，问有多少种不同的方法可以爬到楼顶。
def climb_stairs_dp(n: int) -> int:
"""爬楼梯：动态规划"""
if n <= 2:
return n
# 初始化 dp 表，用于存储子问题的解
dp = [0] * (n + 1)
# 初始状态：已在第 1, 2 阶
dp[1], dp[2] = 1, 2
# 状态转移：从第 3 阶开始
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def climb_stairs_dp_comp(n: int) -> int:
"""爬楼梯：空间优化后的动态规划"""
if n <= 2:
return n
# 仅需存储前两个状态
prev1, prev2 = 1, 2
# 状态转移：从第 3 阶开始
for _ in range(3, n + 1):
curr = prev1 + prev2
prev1, prev2 = prev2, curr
return prev2
3.3 编辑距离问题编辑距离是衡量两个字符串相似度的重要指标，定义为由一个字符串转换成另一个字符串所需的最少编辑操作次数。
def edit_distance_dp(s: str, t: str) -> int:
"""编辑距离：动态规划"""
n, m = len(s), len(t)
# 初始化 dp 表
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 初始化首行首列
for i in range(1, n + 1):
dp[i][0] = i
for j in range(1, m + 1):
dp[0][j] = j
# 状态转移
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == t[j - 1]:
# 两字符相等，不需要编辑
dp[i][j] = dp[i - 1][j - 1]
else:
# 两字符不相等，取三者中的最小值
dp[i][j] = min(
dp[i][j - 1] + 1, # 插入
dp[i - 1][j] + 1, # 删除
dp[i - 1][j - 1] + 1 # 替换
)
return dp[n][m]
4. 动态规划优化技巧4.1 空间优化在许多动态规划问题中，当前状态只依赖于有限的前几个状态，因此可以优化空间复杂度：
def fibonacci(n: int) -> int:
"""斐波那契数列：空间优化后的动态规划"""
if n <= 1:
return n
# 仅需存储前两个状态
prev1, prev2 = 0, 1
# 状态转移
for _ in range(2, n + 1):
curr = prev1 + prev2
prev1, prev2 = prev2, curr
return prev2
4.2 状态压缩对于某些二维DP问题，可以通过状态压缩将空间复杂度从O(n²)降低到O(n)：
def min_path_sum_dp_comp(grid: list[list[int]]) -> int:
"""最小路径和：空间优化后的动态规划"""
n, m = len(grid), len(grid[0])
# 初始化 dp 表
dp = [0] * m
# 初始化首行
dp[0] = grid[0][0]
for j in range(1, m):
dp[j] = dp[j - 1] + grid[0][j]
# 状态转移
for i in range(1, n):
# 首列
dp[0] += grid[i][0]
for j in range(1, m):
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
return dp[m - 1]
5. 动态规划与其他算法的结合5.1 动态规划与贪心算法在某些问题中，贪心算法可以看作是动态规划的一种特殊情况：
def coin_change_greedy(coins: list[int], amt: int) -> int:
"""零钱兑换：贪心"""
# 假设 coins 列表有序
i = len(coins) - 1
count = 0
# 循环进行贪心选择，直到无剩余金额
while amt > 0:
# 找到小于且最接近剩余金额的硬币
while i > 0 and coins[i] > amt:
i -= 1
# 选择 coins[i]
amt -= coins[i]
count += 1
# 若未找到可行方案，则返回 -1
return count if amt == 0 else -1
def coin_change_dp(coins: list[int], amt: int) -> int:
"""零钱兑换：动态规划"""
# 初始化 dp 表
dp = [amt + 1] * (amt + 1)
dp[0] = 0
# 状态转移
for coin in coins:
for a in range(coin, amt + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amt] if dp[amt] != amt + 1 else -1
6. 实践案例在实际应用中，动态规划广泛应用于各种场景：
# 股票买卖问题
def max_profit(prices: list[int]) -> int:
"""买卖股票的最佳时机"""
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
# 最长公共子序列
def longest_common_subsequence(text1: str, text2: str) -> int:
"""最长公共子序列：动态规划"""
n, m = len(text1), len(text2)
# 初始化 dp 表
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 状态转移
for i in range(1, n + 1):
for j in range(1, m + 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[n][m]
总结动态规划是一种强大的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。掌握动态规划的关键在于：
识别问题特征：判断问题是否适合用动态规划解决定义状态：合理定义状态表示问题的子结构建立状态转移方程：找出状态之间的递推关系优化实现：通过空间优化等技巧提高算法效率通过大量练习和实践，我们可以逐步掌握动态规划的精髓，在面对复杂问题时能够灵活运用这一重要算法思想。
参考资料Hello 算法项目: https://www.hello-algo.com/《算法导论》第三版《算法竞赛入门经典》LeetCode算法题库: https://leetcode.com/