跳到主要内容动态规划详解：核心概念与经典案例 | 极客日志Python算法
动态规划详解：核心概念与经典案例
介绍动态规划的基本概念、核心要素及解题步骤。通过 0-1 背包、爬楼梯、编辑距离等经典案例，展示暴力搜索、记忆化搜索及动态规划的实现方法。此外还涵盖空间优化技巧、状态压缩以及与其他算法的结合应用。旨在帮助读者掌握重叠子问题和最优子结构问题的解决思路，提升算法设计能力。
晚风叙旧3 浏览 引言
动态规划是解决具有重叠子问题和最优子结构性质问题的一种算法设计技术。它将复杂问题分解为更小的子问题，通过保存子问题的解来避免重复计算，从而提高算法效率。动态规划广泛应用于最优化问题，如资源分配、路径规划、序列比对等领域。
动态规划基本概念
核心要素
动态规划问题通常具有以下三个核心要素：
- 重叠子问题：问题可以分解为相互重叠的子问题
- 最优子结构：问题的最优解包含子问题的最优解
- 无后效性：某阶段状态一旦确定，不受这个状态以后决策的影响
解题步骤
使用动态规划解决问题通常包括以下步骤：
- 定义状态：确定用哪些变量表示问题的状态
- 状态转移方程：找出状态之间的递推关系
- 初始化：确定初始状态的值
- 计算顺序：确定状态的计算顺序
- 返回结果：根据计算结果返回最终答案
经典动态规划问题
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 背包：暴力搜索"""
if i == 0 or c == 0:
return 0
if wgt[i - 1] > c:
return knapsack_dfs(wgt, val, i - 1, c)
no = knapsack_dfs(wgt, val, i - 1, c)
yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
(no, yes)
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- curl 转代码
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
return
max
记忆化搜索优化
def knapsack_dfs_mem(wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int) -> int:
"""0-1 背包：记忆化搜索"""
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)
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 = [[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:
dp[i][c] = dp[i - 1][c]
else:
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 = [0] * (cap + 1)
for i in range(1, n + 1):
for c in range(cap, 0, -1):
if wgt[i - 1] > c:
dp[c] = dp[c]
else:
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap]
爬楼梯问题
爬楼梯问题是另一个经典的动态规划问题。假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶。
def climb_stairs_dp(n: int) -> int:
"""爬楼梯：动态规划"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
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
for _ in range(3, n + 1):
curr = prev1 + prev2
prev1, prev2 = prev2, curr
return prev2
编辑距离问题
编辑距离是衡量两个字符串相似度的重要指标，定义为由一个字符串转换成另一个字符串所需的最少编辑操作次数。
def edit_distance_dp(s: str, t: str) -> int:
"""编辑距离：动态规划"""
n, m = len(s), len(t)
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]
动态规划优化技巧
空间优化
在许多动态规划问题中，当前状态只依赖于有限的前几个状态，因此可以优化空间复杂度：
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
状态压缩
对于某些二维 DP 问题，可以通过状态压缩将空间复杂度从 O(n²) 降低到 O(n)：
def min_path_sum_dp_comp(grid: list[list[int]]) -> int:
"""最小路径和：空间优化后的动态规划"""
n, m = len(grid), len(grid[0])
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]
动态规划与其他算法的结合
动态规划与贪心算法
在某些问题中，贪心算法可以看作是动态规划的一种特殊情况：
def coin_change_greedy(coins: list[int], amt: int) -> int:
"""零钱兑换：贪心"""
i = len(coins) - 1
count = 0
while amt > 0:
while i > 0 and coins[i] > amt:
i -= 1
amt -= coins[i]
count += 1
return count if amt == 0 else -1
def coin_change_dp(coins: list[int], amt: int) -> int:
"""零钱兑换：动态规划"""
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
实践案例
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 = [[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]
总结
动态规划是一种强大的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。掌握动态规划的关键在于：
- 识别问题特征：判断问题是否适合用动态规划解决
- 定义状态：合理定义状态表示问题的子结构
- 建立状态转移方程：找出状态之间的递推关系
- 优化实现：通过空间优化等技巧提高算法效率
通过大量练习和实践，我们可以逐步掌握动态规划的精髓，在面对复杂问题时能够灵活运用这一重要算法思想。
参考资料
