【学习】《算法图解》第十一章学习笔记：动态规划

一、动态规划概述

动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为更简单的子问题来解决问题的方法。它是一种强大的算法设计技术，特别适用于具有重叠子问题和最优子结构性质的问题。

（一）算法适用场景

动态规划主要适用于以下场景：

最优化问题（求最大值、最小值）
计数问题（求方案数）
具有重叠子问题特性的问题
具有最优子结构特性的问题

（二）算法基本思想

动态规划的核心思想是：

将原问题分解为相互依赖的子问题
求解每个子问题仅一次，并将结果存储在表格中
自底向上地构建解决方案
通过组合子问题的解来得到原问题的解

二、动态规划的关键要素

（一）最优子结构

如果问题的最优解包含其子问题的最优解，则该问题具有最优子结构性质。这是应用动态规划的必要条件。

例如，最短路径问题具有最优子结构：如果从A到C的最短路径经过B，那么A到B的这段路径一定是A到B的最短路径。

（二）重叠子问题

当问题的递归算法会重复计算相同的子问题时，我们称该问题具有重叠子问题特性。动态规划通过存储已解决的子问题的结果来避免重复计算。

例如，计算斐波那契数列时，递归算法会重复计算相同的子问题，而动态规划可以避免这种重复。

（三）状态转移方程

状态转移方程是动态规划的核心，它描述了问题的递推关系，即如何从已解决的子问题推导出更大问题的解。

一般形式：dp[i] = 与dp[i-1], dp[i-2], ...等相关的表达式

三、动态规划的实现方法

（一）自底向上（迭代法）

从最小的子问题开始，逐步构建更大问题的解，最终得到原问题的解。这种方法通常使用数组或表格来存储中间结果。

优点：

避免了递归调用的开销
空间效率通常更高
易于实现和理解

（二）自顶向下（记忆化搜索）

从原问题开始，递归地分解为子问题，但使用缓存（通常是哈希表）存储已解决的子问题的结果，避免重复计算。

优点：

只计算需要的子问题
保持了问题的递归结构
有时更容易实现

四、经典动态规划问题

（一）背包问题

1. 问题描述

有n个物品，每个物品有重量w[i]和价值v[i]。背包最大容量为W。如何选择物品放入背包，使得总价值最大？

2. 状态定义

dp[i][j] 表示考虑前i个物品，背包容量为j时能获得的最大价值。

3. 状态转移方程

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])  如果 j >= w[i]
dp[i][j] = dp[i-1][j]  如果 j < w[i]

4. 代码实现

def knapsack(weights, values, capacity):
    n = len(weights)
    # 创建二维数组
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # 填充dp表
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] <= j:
                # 可以放入背包
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
            else:
                # 不能放入背包
                dp[i][j] = dp[i-1][j]
    
    return dp[n][capacity]

（二）最长公共子序列

1. 问题描述

给定两个序列X和Y，找出它们的最长公共子序列（不要求连续）。

2. 状态定义

dp[i][j] 表示序列X的前i个字符与序列Y的前j个字符的最长公共子序列长度。

3. 状态转移方程

dp[i][j] = dp[i-1][j-1] + 1  如果 X[i-1] == Y[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])  如果 X[i-1] != Y[j-1]

4. 代码实现

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    # 创建二维数组
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    # 填充dp表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 构造最长公共子序列
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs))

（三）编辑距离

1. 问题描述

给定两个字符串str1和str2，计算将str1转换为str2所需的最少操作次数。操作包括：插入、删除和替换字符。

2. 状态定义

dp[i][j] 表示将str1的前i个字符转换为str2的前j个字符所需的最少操作次数。

3. 状态转移方程

dp[i][j] = dp[i-1][j-1]  如果 str1[i-1] == str2[j-1]
dp[i][j] = min(dp[i-1][j] + 1,    # 删除
               dp[i][j-1] + 1,    # 插入
               dp[i-1][j-1] + 1)  # 替换
           如果 str1[i-1] != str2[j-1]

4. 代码实现

def edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    # 创建二维数组
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    # 初始化边界条件
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # 填充dp表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j] + 1,    # 删除
                               dp[i][j-1] + 1,    # 插入
                               dp[i-1][j-1] + 1)  # 替换
    
    return dp[m][n]

五、算法分析

（一）时间复杂度

动态规划的时间复杂度通常取决于状态数量和状态转移的复杂度：

对于一维DP问题：通常为O(n)或O(n²)
对于二维DP问题：通常为O(n²)或O(n³)
对于背包问题：O(n×W)，其中n是物品数量，W是背包容量

（二）空间复杂度

标准动态规划的空间复杂度通常与状态数量相同：

一维DP问题：通常为O(n)
二维DP问题：通常为O(n²)

但许多问题可以通过空间优化（如滚动数组）将空间复杂度降低：

背包问题可以优化到O(W)
某些二维DP问题可以优化到O(n)

（三）算法优缺点

优点：

能够解决具有重叠子问题的复杂问题
避免了递归算法的重复计算
对于特定问题，提供了多项式时间的解决方案

缺点：

状态设计和转移方程推导可能较为复杂
空间需求可能较大
不适用于没有最优子结构的问题

六、动态规划与其他算法的比较

（一）动态规划 vs 贪心算法

特性	动态规划	贪心算法
决策过程	考虑所有可能的子问题解	每步做出局部最优选择
适用条件	最优子结构+重叠子问题	贪心选择性质+最优子结构
复杂度	通常较高	通常较低
正确性	总能得到全局最优解	不一定得到全局最优解

（二）动态规划 vs 分治法

特性	动态规划	分治法
子问题	重叠子问题	独立子问题
解决方式	自底向上或记忆化搜索	递归
存储方式	存储子问题的解	不存储中间结果
典型应用	背包问题、最短路径	归并排序、快速排序

七、动态规划的优化技巧

（一）空间优化

许多动态规划问题可以通过观察状态转移方程，发现当前状态只依赖于有限的前序状态，从而进行空间优化。

1. 滚动数组

使用有限的几个数组交替使用，而不是存储所有状态。

# 背包问题的空间优化版本
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    # 只使用一维数组
    dp = [0 for _ in range(capacity + 1)]
    
    for i in range(n):
        # 逆序遍历，避免覆盖需要的值
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

2. 状态压缩

对于某些问题，可以使用位运算来表示状态，减少空间使用。

（二）预处理和记忆化搜索

对于某些复杂的动态规划问题，可以结合预处理和记忆化搜索来提高效率。

# 记忆化搜索示例
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

八、动态规划的应用场景

（一）实际应用

生物信息学：序列比对、RNA结构预测
自然语言处理：词性标注、语法分析
计算机图形学：图像分割、曲线拟合
运筹学：资源分配、调度问题
金融领域：投资组合优化、期权定价

（二）算法变种

概率动态规划：状态转移具有概率性
区间动态规划：状态定义在区间上
树形动态规划：状态定义在树结构上
数位动态规划：按照数字位数进行状态定义和转移

九、总结

动态规划是一种强大的算法设计技术，特别适用于具有重叠子问题和最优子结构的问题。它通过将复杂问题分解为子问题，并存储子问题的解来避免重复计算，从而提高算法效率。

动态规划的关键步骤包括：

确定状态表示和定义
推导状态转移方程
确定边界条件和初始状态
确定计算顺序
提取最终解

掌握动态规划需要大量的练习和对问题的深入理解。通过不断练习不同类型的动态规划问题，可以培养识别问题特征和设计解决方案的能力。

参考资料

《算法图解》第十一章，Aditya Bhargava 著
Introduction to Algorithms (CLRS)，第15章
Dynamic Programming for Coding Interviews，Meenakshi & Kamal Rawat 著
维基百科：动态规划
MIT OpenCourseWare: Dynamic Programming

学习

#算法 #《算法图解》 #动态规划 #最优化问题

【学习】《算法图解》第十二章学习笔记：K近邻算法上一篇

【学习】《算法图解》第十章学习笔记：贪婪算法下一篇