第15章 动态规划

导读

动态规划（Dynamic Programming, DP）是算法设计中最重要的策略之一，适用于具有重叠子问题和最优子结构性质的优化问题。动态规划的核心思想是将复杂问题分解为子问题，通过保存子问题的解来避免重复计算，从而将指数级时间复杂度降低到多项式级别。

本章将系统介绍动态规划的设计思想、实现方法和经典应用。从钢条切割、矩阵链乘法到最长公共子序列，我们将通过一系列经典问题来掌握动态规划的精髓。

核心概念详解

15.1 动态规划的基本思想

动态规划适用于具有以下两个性质的问题：

最优子结构（Optimal Substructure）：

问题的最优解包含子问题的最优解。即可以通过组合子问题的最优解来得到原问题的最优解。

重叠子问题（Overlapping Subproblems）：

递归算法会反复求解相同的子问题。动态规划通过保存子问题的解来避免重复计算。

两种实现方式：

自顶向下（带备忘的递归）：

MEMOIZED-CUT-ROD(p, n)
    if r[n] ≥ 0
        return r[n]
    if n == 0
        q = 0
    else
        q = -∞
        for i = 1 to n
            q = max(q, p[i] + MEMOIZED-CUT-ROD(p, n - i))
    r[n] = q
    return q

自底向上（迭代）：

BOTTOM-UP-CUT-ROD(p, n)
    r[0] = 0
    for j = 1 to n
        q = -∞
        for i = 1 to j
            q = max(q, p[i] + r[j - i])
        r[j] = q
    return r[n]

15.2 动态规划设计步骤

刻画最优解的结构特征：分析问题的最优解如何由子问题的最优解构成。

递归定义最优解的值：建立递归关系（状态转移方程）。

自底向上计算最优解的值：通常使用数组保存子问题的解。

构造最优解（可选）：根据保存的信息重构最优解。

15.3 钢条切割问题

问题描述：

给定长度为n英寸的钢条和价格表p[i]（长度为i英寸的钢条价格），求切割方案使收益最大。

状态定义：

r[n] = 长度为n的钢条的最大收益

状态转移方程：

r[n] = max(p[i] + r[n-i])，i从1到n

时间复杂度：

• 朴素递归：O(2^n)（指数级）
• 带备忘的递归：O(n²)
• 自底向上：O(n²)
• 空间：O(n)

15.4 矩阵链乘法

问题描述：

给定n个矩阵的链⟨A₁, A₂, ..., Aₙ⟩，确定乘法顺序使标量乘法次数最少。

关键观察：

矩阵乘法满足结合律，不同的乘法顺序导致不同的计算代价。

例如：(A₁A₂)A₃ vs A₁(A₂A₃)

状态定义：

m[i,j] = 计算Aᵢ...Aⱼ的最小代价

状态转移方程：

m[i,j] = min{m[i,k] + m[k+1,j] + pᵢ₋₁·pₖ·pⱼ}，k从i到j-1

实现：

MATRIX-CHAIN-ORDER(p)
    n = p.length - 1
    for i = 1 to n
        m[i,i] = 0
    for l = 2 to n          // l为链长
        for i = 1 to n - l + 1
            j = i + l - 1
            m[i,j] = ∞
            for k = i to j - 1
                q = m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j]
                if q < m[i,j]
                    m[i,j] = q
                    s[i,j] = k
    return m and s

时间复杂度：O(n³)

空间复杂度：O(n²)

15.5 最长公共子序列（LCS）

问题描述：

给定两个序列X和Y，找最长的公共子序列。

子序列：从原序列中删除若干元素（可以不删除）得到的序列，保持相对顺序。

状态定义：

c[i,j] = X[1..i]和Y[1..j]的LCS长度

状态转移方程：

如果X[i] = Y[j]：
    c[i,j] = c[i-1,j-1] + 1
否则：
    c[i,j] = max(c[i,j-1], c[i-1,j])

实现：

LCS-LENGTH(X, Y)
    m = X.length, n = Y.length
    for i = 0 to m
        c[i,0] = 0
    for j = 0 to n
        c[0,j] = 0
    for i = 1 to m
        for j = 1 to n
            if X[i] == Y[j]
                c[i,j] = c[i-1,j-1] + 1
                b[i,j] = "↖"
            else if c[i-1,j] ≥ c[i,j-1]
                c[i,j] = c[i-1,j]
                b[i,j] = "↑"
            else
                c[i,j] = c[i,j-1]
                b[i,j] = "←"
    return c and b

时间复杂度：O(mn)

空间复杂度：O(mn)

15.6 最优二叉搜索树

问题描述：

给定n个关键字的搜索概率，构建二叉搜索树使期望搜索代价最小。

状态定义：

e[i,j] = 包含关键字kᵢ...kⱼ的最优BST的期望搜索代价

状态转移方程：

e[i,j] = min{e[i,r-1] + e[r+1,j] + w(i,j)}，r从i到j

其中w(i,j)为子树的概率和。

15.7 动态规划的要素

子问题图：

子问题图是一个有向图，每个节点对应一个子问题，边表示依赖关系。子问题图的规模决定了动态规划的时间复杂度。

子问题的大小：

通常用参数的个数或范围来衡量。例如LCS问题中，子问题由(i,j)两个参数确定。

15.8 空间优化

许多动态规划问题可以优化空间：

滚动数组：

如果当前状态只依赖前一层的几个状态，可以用滚动数组减少空间。

LCS的空间优化：

c[i,j]只依赖c[i-1,j-1]、c[i-1,j]和c[i,j-1]，可以用两行数组代替整个二维数组，空间从O(mn)降到O(min(m,n))。

15.9 动态规划与贪心的关系

动态规划和贪心都基于最优子结构，但关键区别在于：

• 贪心：每步做局部最优选择，不回溯
• 动态规划：考虑所有可能的选择，选择最优

贪心要求"贪心选择性质"——局部最优选择能导致全局最优。动态规划不要求这个性质。

15.10 经典动态规划问题

0-1背包问题：

• n个物品，每个有重量wᵢ和价值vᵢ
• 背包容量W
• 求最大价值

状态：dp[i][w] = 前i个物品、容量w时的最大价值

转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ)

最长递增子序列（LIS）：

状态：dp[i] = 以第i个元素结尾的LIS长度

转移：dp[i] = max(dp[j] + 1)，j < i且a[j] < a[i]

编辑距离：

状态：dp[i][j] = 将X[1..i]转换为Y[1..j]的最小操作数

转移：考虑插入、删除、替换三种操作

硬币找零：

状态：dp[w] = 凑成金额w的最少硬币数

转移：dp[w] = min(dp[w-cᵢ] + 1)

重要知识点

知识点1：最优子结构的证明

证明问题具有最优子结构通常使用"剪切-粘贴"技术：

• 假设最优解不包含子问题的最优解
• 用子问题的最优解替换，得到更优的解
• 矛盾，因此最优解必须包含子问题的最优解

知识点2：重叠子问题的识别

重叠子问题意味着递归树中有大量重复的子问题。通过画出递归树，可以直观地看到子问题的重叠情况。

知识点3：状态转移方程的设计

状态转移方程是动态规划的核心。设计时需要考虑：

• 状态的定义（哪些参数）
• 状态之间的转移关系
• 边界条件

知识点4：自顶向下vs自底向上

• 自顶向下（记忆化搜索）：自然直观，但递归开销大
• 自底向上（迭代）：避免递归开销，但需要确定计算顺序

知识点5：空间优化的技巧

许多DP问题可以通过分析状态依赖关系来优化空间。常见技巧：

• 滚动数组
• 只保存必要的状态
• 重新设计状态定义

常见误区

误区1：所有问题都可以用动态规划解决

动态规划只适用于具有最优子结构和重叠子问题的问题。不是所有问题都满足这些条件。

误区2：动态规划总是比贪心好

如果问题具有贪心选择性质，贪心算法更简单高效。动态规划适用于贪心不适用的情况。

误区3：动态规划的时间复杂度总是多项式

动态规划的时间复杂度取决于子问题的数量和每个子问题的计算时间。某些问题的子问题数量可能是指数的。

误区4：状态定义是唯一的

同一个问题可能有多种状态定义方式，不同的定义可能导致不同的时间复杂度。选择好的状态定义是关键。

误区5：动态规划不需要证明正确性

动态规划的正确性依赖于最优子结构和状态转移方程的正确性。需要严格证明。

实践应用

应用1：生物信息学

动态规划在序列比对中广泛应用：

• Needleman-Wunsch算法（全局比对）
• Smith-Waterman算法（局部比对）
• 基因序列分析

应用2：自然语言处理

• 分词算法
• 词性标注（Viterbi算法）
• 机器翻译（对齐模型）

应用3：计算机视觉

• 动态时间规整（DTW）
• 图像分割
• 目标跟踪

应用4：金融工程

• 期权定价
• 投资组合优化
• 风险管理

应用5：资源调度

• 任务调度
• 内存分配
• 网络路由

15.11 动态规划的更多经典问题

0-1背包问题的详细分析：

问题：n个物品，重量w₁...wₙ，价值v₁...vₙ，背包容量W。求最大价值。

状态定义：dp[i][w] = 前i个物品、容量w时的最大价值

状态转移：

dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]] + v[i])  // 不选/选第i个物品

时间复杂度：O(nW)，空间复杂度：O(nW)，可优化到O(W)。

注意：这不是多项式时间算法，因为W的编码长度是log W，所以nW相对于输入规模是指数级的。

最长递增子序列（LIS）的详细分析：

问题：找最长严格递增的子序列。

方法1（DP）：

• dp[i] = 以a[i]结尾的LIS长度
• dp[i] = max(dp[j] + 1)，j < i且a[j] < a[i]
• 时间O(n²)

方法2（DP+二分）：

• 维护一个tails数组，tails[i]存储长度为i+1的递增子序列的最小末尾
• 对每个元素，用二分查找找到它在tails中的位置
• 时间O(n log n)

编辑距离（Levenshtein距离）：

问题：将字符串X转换为Y的最少操作数（插入、删除、替换）。

状态：dp[i][j] = X[1..i]转换为Y[1..j]的最少操作数

转移：

如果X[i] == Y[j]：dp[i][j] = dp[i-1][j-1]
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

分别对应删除、插入、替换。

15.12 动态规划的状态设计技巧

状态压缩：

当状态空间太大时，需要巧妙设计状态定义来减少状态数。例如：

• 旅行商问题的状态压缩DP（状压DP）：dp[S][i]表示已访问集合S、当前在i的最短路径
• 时间O(n²·2ⁿ)，适用于n较小的情况

状态扩展：

有时需要增加状态维度来捕获更多信息。例如：

• 带约束的最短路径：dp[v][k]表示到顶点v、使用k条边的最短路径
• 股票买卖问题：dp[i][j][k]表示第i天、持有j股、已交易k次的最大利润

区间DP：

状态为区间[i,j]的DP。计算顺序按区间长度递增。

• 矩阵链乘法
• 石子合并
• 最优BST

树形DP：

在树上进行DP，通常后序遍历保证子问题先求解。

• 树的最大独立集
• 树的直径
• 树上路径问题

15.13 动态规划与记忆化搜索的对比

记忆化搜索的优势：

• 只计算需要的状态（惰性求值）
• 代码更直观，直接对应递归定义
• 适合状态空间稀疏的情况

迭代DP的优势：

• 无递归开销（函数调用、栈帧）
• 可以精确控制计算顺序
• 更容易进行空间优化
• 缓存友好（顺序访问数组）

选择建议：

• 状态空间稠密：优先迭代DP
• 状态空间稀疏：优先记忆化搜索
• 需要空间优化：迭代DP更容易
• 快速原型：记忆化搜索更直观

15.14 动态规划在实际系统中的广泛应用

生物信息学：

• Needleman-Wunsch算法：全局序列比对
• Smith-Waterman算法：局部序列比对
• 隐马尔可夫模型中的Viterbi算法

自然语言处理：

• 中文分词
• 词性标注
• 语音识别中的动态时间规整

计算机视觉：

• seam carving（内容感知图像缩放）
• 立体匹配
• 目标跟踪

金融工程：

• 期权定价的二叉树模型
• 投资组合优化
• 风险管理中的VaR计算

本章小结

本章深入介绍了动态规划的设计思想和方法。我们学习了：

基本思想：通过保存子问题的解避免重复计算，将指数时间降为多项式时间。

两个关键性质：最优子结构和重叠子问题。

设计步骤：刻画结构、递归定义、自底向上计算、构造最优解。

经典问题：钢条切割、矩阵链乘法、最长公共子序列、最优二叉搜索树、0-1背包、LIS、编辑距离等。

实现方式：自顶向下（记忆化）和自底向上（迭代），各有优劣。

状态设计技巧：状态压缩、状态扩展、区间DP、树形DP等。

空间优化：滚动数组等技巧减少空间使用。

实际应用：生物信息学、自然语言处理、计算机视觉、金融工程等领域。

动态规划是算法设计中最强大的工具之一。掌握动态规划的思想和方法，能够解决大量复杂的优化问题。

关键术语

思考题

设计一个动态规划算法，找出不超过n的最大斐波那契数。

分析矩阵链乘法问题中，如果所有矩阵大小相同，最优解是什么。

设计一个O(n)时间的算法，找出数组中和最大的连续子数组（Kadane算法）。

证明：0-1背包问题不具有贪心选择性质。