动态规划详解：核心概念与经典案例

记忆化搜索优化

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]

爬楼梯问题

爬楼梯问题是另一个经典的动态规划问题。假设你正在爬楼梯，需要 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

编辑距离问题

编辑距离是衡量两个字符串相似度的重要指标，定义为由一个字符串转换成另一个字符串所需的最少编辑操作次数。

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]

动态规划优化技巧

空间优化

在许多动态规划问题中，当前状态只依赖于有限的前几个状态，因此可以优化空间复杂度：

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 表
    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:
    """零钱兑换：贪心"""
    # 假设 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

实践案例

在实际应用中，动态规划广泛应用于各种场景：

# 股票买卖问题
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]

总结

动态规划是一种强大的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。掌握动态规划的关键在于：

1. 识别问题特征：判断问题是否适合用动态规划解决
2. 定义状态：合理定义状态表示问题的子结构
3. 建立状态转移方程：找出状态之间的递推关系
4. 优化实现：通过空间优化等技巧提高算法效率

通过大量练习和实践，我们可以逐步掌握动态规划的精髓，在面对复杂问题时能够灵活运用这一重要算法思想。

参考资料

1. 《算法导论》第三版
2. 《算法竞赛入门经典》