第七章 动态规划

参考资料：动态规划法 AOE网络（最长路径） 弗洛伊德算法 最长公共子序列 01背包问题 https://www.bilibili.com/video/BV1L54y1U7zP

7.2 Floyd

7.2.1 递推关系

设 $D^{(k)}[i][j]$ 表示从节点 $i$ 到节点 $j$ 且中间节点编号不超过 $k$ 的最短路径长度。

递推关系：对于每个中间节点 $k$，有两种情况：

1. 不经过 $k$：路径保持原值，即 $D^{(k)}[i][j] = D^{(k-1)}[i][j]$
2. 经过 $k$：路径拆分为 $i \to k$ 和 $k \to j$，即 $D^{(k)}[i][j] = D^{(k-1)}[i][k] + D^{(k-1)}[k][j]$
   实际实现中，我们可以将 $k$ 从 0 到 n 枚举，覆盖更新，就不再需要 k 这一维了。

简化版的状态转移：

$D[i][j] = \min\left(D[i][j], D[i][k] + D[k][j]\right)$

伪代码：
枚举顺序 $k \to i \to j$

for k: 0->n
    for i: 0->n
        for j: 0->n
            if(i~k~j 小于 i~j)
                d[i][j] = d[i][k] + d[k][j]

7.2.2 记录路径

引入一个额外的二维数组 next，其中 next[i][j] 表示从节点 $i$ 到节点 $j$ 的最短路径中，$i$ 的下一个节点。

• 初始化：

  • 如果 $i$ 和 $j$ 之间有边，则 next[i][j] = j
  • 否则，next[i][j] = -1

• 更新规则：

  • 当发现更短的路径时，更新 dist[i][j] 和 next[i][j]
  • next[i][j] 被设置为 next[i][k]，因为路径从 $i$ 经过 $k$ 到 $j$

• 路径打印：

  • 使用 next 数组回溯路径，从 $i$ 开始，沿着 next 数组直到 $j$

假设图的邻接矩阵如下：

调用 floyd 算法后，dist 和 next 数组如下：

代码演示（gpt-4o-mini生成，可以丢给AI解释）

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

void floydWarshall(int n, vector<vector<int>>& graph, vector<vector<int>>& dist, vector<vector<int>>& next) {
    // Initialize distance and next matrices
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != INF && i != j) {
                next[i][j] = j;
            } else {
                next[i][j] = -1; // No path
            }
        }
    }

    // Floyd-Warshall algorithm
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
}

void printPath(int u, int v, const vector<vector<int>>& next) {
    if (next[u][v] == -1) {
        cout << "No path from " << u << " to " << v << endl;
        return;
    }
    cout << "Path from " << u << " to " << v << ": ";
    while (u != v) {
        cout << u << " ";
        u = next[u][v];
    }
    cout << v << endl;
}

int main() {
    int n = 4; // Number of vertices
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, INF));
    vector<vector<int>> dist(n + 1, vector<int>(n + 1));
    vector<vector<int>> next(n + 1, vector<int>(n + 1));

    // Example graph initialization (0: no edge, INF: no path)
    graph[1][1] = 0;
    graph[1][2] = 3;
    graph[1][3] = INF;
    graph[1][4] = 7;
    graph[2][1] = 8;
    graph[2][2] = 0;
    graph[2][3] = 2;
    graph[2][4] = INF;
    graph[3][1] = 5;
    graph[3][2] = INF;
    graph[3][3] = 0;
    graph[3][4] = 1;
    graph[4][1] = 2;
    graph[4][2] = INF;
    graph[4][3] = INF;
    graph[4][4] = 0;

    floydWarshall(n, graph, dist, next);

    // Print final path and distance matrices
    cout << "Distance Matrix:" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }

    cout << "Path Matrix:" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << next[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

7.3 矩阵连乘

$A_{i}A_{i+1}...A{j}$

矩阵 $A_i$ 行数 $p_i$，列数 $q_i$
后一个矩阵的行数必等于前一个矩阵的列数，矩阵是这样用一维数组存储的：{p1, q1(p2), q2(p3), ...}
例如，$\{ 10, 30, 5, 60 \}$ 表示 $A_1(10*30), A_2(30*5), A_3(5*60)$ (ps. 本例答案为4500)

7.3.1 普通动态规划

自底向上：通过 迭代 预先计算所有可能的子问题，按子链长度从小到大的顺序填充表格。

记 $m[i][j]$ 为从 i 到 j 最少乘法次数，那么：

• 对 $i \sim j$ 中任意一个数 $k$，$m[i][k], m[k+1][j]$ 也都是最少的 [最优子结构性质]
• $m[i][i]=0$ [一个矩阵不用做乘法]
• 当 $i < j$ 时，$m[i][j]= min \{ m[i][k] + m[k+1][j] + \text{(一次乘法操作)} \}$，其中 $i \leq k < j$

(一次乘法操作)= $p_i*q_k*q_j$
根据本节开头提到的性质，(一次乘法操作)可以改写为 $q_{i-1}*q_k*q_j$。
这样改写的好处是，矩阵可以简化为用一维数组保存。

7.3.2 备忘录方法

自顶向下：通过 递归 分解问题，遇到子问题时先查表，若未计算则递归求解并保存结果，按需填充表格。

记 $m[i][j]$ 为从 i 到 j 最少乘法次数，$Memo(i, j)$ 从 i 到 j 最少乘法次数的递归函数，那么：

• $m[i][i]=0$ [一个矩阵不用做乘法]
• 其他的 $m[i][j]$ 均初始化为 -1
• 如果 $m[i][j] \neq -1$ 说明子问题已经计算过，直接返回
• 当 $i < j$ 时，$m[i][j]= Memo(i, k) + Memo(k+1, j) + \text{(一次乘法操作)}$

上述两种方法时间复杂度都是 $O(n^3)$，空间复杂度都是 $O(n^2)$

7.4 最长公共子序列LCS

$S1=ABCBDAB (len=7) \\ S2=BDCABC (len=6) \\ LCS=BCAB$

记 $dp[i][j]$ 为 S1 前 i 个字符、S2 前 j 个字符的 LCS，则例题所要求的就是 $dp[7][6]$.

状态如何转移？

1. $dp[i][0] = dp[0][j] = 0$，长度为0哪来的子序列
2. $S1[i] == S2[j]$ 匹配上了，皆大欢喜，$dp[i][j] = dp[i-1][j-1] + 1$
3. $S1[i] \neq S2[j]$ 没匹配上，只能选前面最大的，$dp[i][j] = max\{ dp[i-1][j], dp[i][j-1]\}$

时间复杂度：$O(n^2)$

7.5** 最优二叉搜索树

p143 例7.7
p159 习题7.13

Optimal Binary Search Tree = OBST 书上讲的啥玩意，看不懂
如何做题：https://www.bilibili.com/video/BV1oTcUexE8T

建议看视频时对照看下面的内容：

$p$ 矩阵是查找成功的概率， $q$ 矩阵是查找失败的概率
$(w,c,r)$ 矩阵：我们目的是，让 $c[0][n]$ 最小

$w(i,j)$: Weight, 表示 $a_i$ 到 $a_j$ 的总概率，既包括成功也包括失败
例：$w(1,2)$ 为什么等于 $p1+p2+q0+q1+q2$ 请看下图，星号表示查找失败

         a₂(p2)
        /     \
      a₁(p1)   *(q2)
     /    \ 
   *(q0)  *(q1)

对于其他的树形，仍然是这几个概率相加不变

$c(i,j)$: Cost, 表示 $a_i$ 到 $a_j$ 内构造OBST的最小平均搜索代价
由最优子结构，我们把从 i 到 j 挨个作为根，看谁作为根的时候，(左子树代价+右子树代价) 最小，此时 $c(i,j)$ 就是最小。
$c(i,j) = min\{ c(i,k-1) + c(k,j)\} + w(i,j) ...其中 i < k \leq j$
联想一下矩阵连乘，递推式几乎就是同一个意思，只是把(一次乘法操作)改成了w(i,j)即$a_i$ 到 $a_j$ 的总概率。

$r(i,j)$: Root, 当 $a_i$ 到 $a_j$ 代价最小时，把谁作为根？

ps. 《算法导论》（原书第三版） 15.5 最优二叉搜索树
注意算法导论解此问题，i是从1开始的，j是从0开始的。而陈的《算法设计与分析》中i和j都是从0开始。算法导论p230的推导，答案为 $e(1,5)$。如果想按照陈的书来理解，把i下标整体减1就能看懂了。

7.6 01背包

7.6.1 一般方法

设背包容量6，物品如下：

记 $dp[i][j]$ 表示仅能在前 i 件物品里面选、放入大小为 j 的背包中，得到的最大价值。例题要求的就是 $dp[5][6]$.

状态如何转移？

1. $dp[i][0] = dp[0][j] = 0$，没有物品/背包容量为0，肯定没有价值
2. $j < w[i]$，背包的容量装不下第 i 件物品，选不了第 i 件物品。 $dp[i][j] = dp[i-1][j]$
3. $j >= w[i]$，背包的容量能装下第 i 件物品，此时考虑选不选第 i 件。 $dp[i][j] = max(选第i件, 不选第i件)$
4. 若选第 i 件，价值为
   (第 i 件物品的价值) + (前 i-1 件物品、放入去掉第 i 件物品重量的背包、得到的最大价值)
   即 $dp[i-1][j-w[i]] + v[i]$
5. 若不选第 i 件，价值就还是 $dp[i-1][j]$

时间复杂度：$O(nm)$，其中n表示物品的数量，m表示背包的容量

7.6.2* 阶跃点法

阶跃点求解0-1背包问题_哔哩哔哩_bilibili

-, 视频播放量 27、弹幕量 0、点赞数 0、投硬币枚数 0、收藏人数 0、转发人数 0, 视频作者 亦是远方, 作者简介 一个程序员，相关视频：最优二叉搜索树，15迷问题，最佳合并模式，蓝桥杯三十天冲刺：动态规划-01背包1，单纯形方法，P2：LL(1)语法分析程序之求解First集合，蓝桥杯三十天冲刺：动态规划-01背包空间优化，【DeepSeek教程】清华大学DeepSeek从入门到精通，全程干货无废话！少走99%的弯路！存下吧，很难找全的！！（三联教学费，白嫖学不会），全套Kali渗透教程（2025最全最细新手入门）手把手带你从入门到入狱，再也不用盲目自学了！，【清华大学】DeepSeek从入门到精通，全程干货无废话！让你少走99%的弯路！（三联教学费，白嫖学不会）逼自己一周学完，AI大模型技术猛涨！

www.bilibili.com

阶跃点（Step Points） 表示在不同背包容量下，能够达到的最优（重量，价值）组合。
每个阶跃点集合 $S_i$ 表示处理前 $i+1$ 个物品后的状态。

剔除被支配点：两个阶跃点A（W1, V1）和B（W2, V2），如果W1 ≤ W2且V1 ≥ V2，那么B点被支配，应该剔除。
即，A点花费了更少的容量，得到了更大的价值，必定比B点更优。就不要B点了。

设背包容量6，物品如下：

(1) 初始状态 $S^{-1}$（未放入任何物品）

• 初始状态为空背包，仅包含原点：

  $$S^{-1} = \{(0, 0)\}$$

(2) 处理第0个物品（重量1.8，价值2） → 生成 $S^{0}$

• 不放入物品0：保留 $S^{-1}$ 的所有点 $\{(0, 0)\}$。
• 放入物品0（记为 $S^0_1$）：生成新点 $(1.8, 2)$。

• 合并并剔除被支配的点：

  • 比较 $(0, 0)$ 和 $(1.8, 2)$，均未被支配。

  • 最终集合：

    $$S^{0} = \{(0, 0), (1.8, 2)\}$$

(3) 处理第1个物品（重量3.2，价值3） → 生成 $S^{1}$

• 不放入物品1：保留 $S^{0}$ 的所有点 $\{(0, 0), (1.8, 2)\}$。

• 放入物品1（记为 $S^1_1$）：对 $S^{0}$ 中的每个点 $(w, v)$，生成新点 $(w+3.2, v+3)$：

  • $(0+3.2, 0+3) = (3.2, 3)$
  • $(1.8+3.2, 2+3) = (5.0, 5)$

• 合并并剔除被支配的点：

  • 原集合 $S^{0}$ $\{(0,0), (1.8,2)\}$ 与新集合 $S^1_1$ $\{(3.2,3), (5.0,5)\}$ 合并。
  • 剔除被支配的点（例如，$(3.2,3)$ 未被任何点支配）。

  • 最终集合：

    $$S^{1} = \{(0, 0), (1.8, 2), (3.2, 3), (5.0, 5)\}$$

(4) 处理第2个物品（重量2.5，价值5） → 生成 $S^{2}$

• 不放入物品2：保留 $S^{1}$ 的所有点。

• 放入物品2（记为 $S^2_1$）：对 $S^{1}$ 中的每个点 $(w, v)$，生成新点 $(w+2.5, v+5)$：

  • $(0+2.5, 0+5) = (2.5, 5)$
  • $(1.8+2.5, 2+5) = (4.3, 7)$
  • $(3.2+2.5, 3+5) = (5.7, 8)$
  • $(5.0+2.5, 5+5) = (7.5, 10)$（超出容量6，舍去）

• 合并并剔除被支配的点：

  • 原集合 $S^{1}$ $\{(0,0), (1.8,2), (3.2,3), (5.0,5)\}$ 与新集合 $S^2_1$ $\{(2.5,5), (4.3,7), (5.7,8)\}$ 合并。
  • 剔除被支配的点：$(2.5,5)$ 比 $(3.2,3), (5,5)$ 更优。
  • $(5.7,8)$ 是最大价值点。

  • 最终集合：

    $$S^{2} = \{(0, 0), (1.8, 2), (2.5, 5), (4.3, 7), (5.7, 8)\}$$

(5) 逆序求解选了哪些物品

如果上面的步骤看懂了，直接看视频 5:09

本例答案：

$(5.7,8) \in S^2_1 \text{还是} S^1? ==> S^2_1 \therefore x2=1$
$(3.2,3) \in S^1_1 \text{还是} S^0? ==> S^1_1 \therefore x1=1$
$(0,0) \in S^0_1 \text{还是} S^{-1}? ==> S^{-1} \therefore x0=0$

$x=(x0,x1,x2)= \{ 0,1,1 \}$

7.7 (双机)流水作业调度

这和动态规划有什么关系？

$n$个作业 $(1,2,...,n)$ 要在由两台机器 $M1$ 和 $M2$ 组成的流水线上完成加工。
每个作业加工的顺序都是先在 $M1$ 上加工，然后在 $M2$ 上加工。
$M1$ 和 $M2$ 加工作业 $i$ 所需的时间分别为 $a_i$ 和 $b_i$。
求最优加工顺序，使得用时最少。

Johnson 算法：

1. 所有 $a_i \lt b_i$ 的作业，划归为集合 $N_1$；所有 $a_i \geq b_i$ 的作业，划归为集合 $N_2$.
2. 将 $N_1$ 中的作业按照 $a_i$ 递增排序，$N_2$ 中的作业按照 $b_i$ 递减排序.
3. $N_1$ 中作业接 $N_2$ 中作业，构成满足 Johnson 法则的最优调度。
4. 最优加工顺序：$N_1$ 中的作业、$N_2$ 中作业

$N_1: \{ J_1, J_2, J_5 \}$ 排序后 {2, 5, 1}
$N_2: \{ J_3, J_4, J_6 \}$ 排序后 {6, 4, 3}
最优加工顺序： {2, 5, 1, 6, 4, 3}