Czj's Blog

动态规划

发表于
本文字数： 10k 阅读时长 ≈ 9 分钟

动态规划

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

20 世纪 50 年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

当问题具有最优子结构并且可以使用自底向上方法解决时，使用动态规划。动态规划方法通过两种技术(记忆和制表)扩展了分而治之的方法，这两种技术都具有存储和重用子问题解决方案的目的，可以极大地提高性能。例如，斐波那契函数的朴素递归实现的时间复杂度为 \(O(2^n)\)，而 DP 解决方案只需要 \(O(n)\) 时间就可以完成同样的工作。

记忆(自顶向下缓存填充)是指缓存和重用先前计算结果的技术。因此，记忆 fib 函数看起来像这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

memory_fibonacci(n) {

    if (memory[n] is undefined)

        if (n < 2) result = n

        else result = memory_fibonacci(n-2) + memory_fibonacci(n-1)

        memory[n] = result

    returnmemory[n]

}

制表(自底向上的缓存填充)与此类似，但重点是填充缓存的条目。计算缓存中的值最简单的方法是迭代。fib 的制表版本是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

tab_fibnocci(n) {

    memory[0] = 0

    memory[1] = 1

    for i = 2...n

        memory[i] = memory[i-2] + memory[i-1]

    returnmemory[n]

}

这里应该掌握的主要思想是，由于分治问题具有重叠的子问题，因此可以缓存子问题的解决方案，从而实现记忆/制表。

状态转移方程

动态规划的核心是找到状态转移方程。例如给定一个数字三角形

1
2
3
4
5
6
7
8
9
10
11

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

从上到下选择一条路，使得经过的数字之和最大。路径上的每一步只能往下或者右下走。

【递归解法】DFS 深搜

可以看出每走第 \(n\) 行第 \(m\) 列时有两种后续：向下或者向右下。由于最后一行可以确定，当做边界条件，所以我们自然而然想到递归求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

inta[101][101];

int n;

intdfs(i, j){

  if(i == n):

    returna[i][j];

  int x = dfs(i+1, j);

  int y = dfs(i+1, j+1);

  returnmax(x, y) + a[i][j];

}


其实仔细观察，上面的解答过程时间复杂度难以想象的大，那是因为对有的数字的解进行了多次的重复计算，如果每次都把结果保存下来，复杂度就会大大降低。

设 \(dp[i][j]\) 表示到达位置 \((i,j)\) 时获得的最大数字和。显然到达 \((i,j)\)，只能通过 \((i-1, j)\) 和 \((i-1, j-1)\) 这两个位置，选择其中最大的并加上当前值即可，所以转移方程为

\[ dp[i][j] = \max(dp[i-1][j], dp[i-1][j-1]) + a[i][j] \]

1
2
3
4
5
6
7
8
9

dp[0][0] = a[0][0]

for(int i = 1; i <= n; i++)

  for(int j = 1; j <= n; j++)

      dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j]

背包问题

0/1 背包

题目描述 给定有 \(n\) 件物品和一个容量为 \(C\) 的背包。第 \(i\) 件物品的体积是 \(c_i\) ，价值是 \(v_i\)。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

暴力深搜 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是 \(O(2^n)\)，这里的 \(n\) 表示物品数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int ans = 0; // 记录最大价值

int c[], int v[];

int n, C;

// 回溯法求解 0/1 背包

voidks_dfs(inti, intj, intk) { // i 表示物品，j表示容量，k表示当前获得的价值

    //已经考虑了n个物品

    if (i == n) {

        ans = max(ans, k);

        return;

    }


    // 选择当前物品（前提是不会超重）

    if (j + c[i] <= C) {

        ks_dfs(i + 1, j + c[i], k + v[i]);

    }


    // 不选择当前物品

    ks_dfs(i + 1, j, k);

}

暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

动态规划 引入一个二维数组 \(dp[i][j]\)表示把前 \(i\) 个(从第 \(1\) 个到第 \(i\) 个物品)物品装入容量为 \(j\) 的背包中获得的最大价值。最后 \(dp[n][C]\) 就是将 \(n\) 个物品装入容量为 \(C\) 的背包获得的最大价值。

转移方程 用自底向上的方法计算，如果递推到 \(dp[i][j]\)，即：将第 \(i\) 个物品放入到容量为 \(j\) 的背包，有两种情况：

  1. 第 \(i\) 个物品的体积 \(c[i] > j\)，无法放入背包，那么这是所获得的最大价值等于前 \(i-1\) 个物品获得的最大价值，即 \(dp[i][j] = dp[i-1][j]\)。

  2. 第 \(i\) 个物品的体积 \(c_i \le j\)，可以放入背包。这时候也考虑两种情况：

    1. 如果不加入第 \(i\) 个物品，则 \(dp[i][j] = dp[i-1][j]\)。

    2. 如果加入第 \(i\) 个物品，则背包容量减少 \(c[i]\)，价值增加 \(v[i]\)，所以获得价值 \(dp[i][j] = dp[i-1][j-c[i]] + v[i]\)。

这时候取这两种情况最大的值，所以转移方程为：

\[ dp[i][j] = max\{dp[i-1][j], dp[i-1][j-c[i]] + v[i]\} \]

例如，c[]={2, 3, 6, 5}，v[]={6, 3, 5, 4}，C=9。

alt text

递推代码 自底向上的递推代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

intksi(intn, intC) {

  for(int i = 1; i <= n; i++) //遍历物品

    for(int j = 1; j <= C; j++) //遍历容量

      if(c[i] > j) //放不下

        dp[i][j] = dp[i-1][j];

      else

        dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + v[i]); //放与不放的最大值



  returndp[n][C];

}

递归代码 自顶向下的记忆化递归代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

intksr(inti, intj) {

    if(dp[i][j] != 0) returndp[i][j]; //注意dp[i][j]需要预先初始化为0


    if(i == 0 || j == 0) return0;


    int res;


    if(c[i] > j)

      res = ksr(i-1, j);

    else

      res = max(ksr(i-1, j), ksr(i-1, j-c[i]) + v[i]);



    returndp[i][j] = res;

}

容易得到，上述算法的时间复杂度是 \(O(nC)\)，空间复杂度也是 \(O(nC)\)。

空间优化 从上面分析过程可以看到转移方程中，计算 \(dp[i][j]\)时，仅仅与 \(dp[i-1][j]\) 有关，所以通过交替滚动的方式来优化空间。

定义 \(dp[2][j]\)，利用\(dp[1][j]\) 和 \(dp[0][j]\)交替滚动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

intdp[2][C+1];


intksi(intn, intC) {

    int now = 0;

    for(int i = 1; i <= n; i++) {

      now = i & 1;

      for(int j = 1; j <= C; j++)

        if(c[i] > j)

            dp[now][j] = dp[now^1][j];

        else

            dp[now][j] = max(dp[now^i][j], dp[now^1][j-c[i]] + v[i]);

    }


    returndp[now][C];

}

滚动数组可以用 swap(old, new) 方式实现，上面代码中用与和或运算也是一种常见的技巧。

可以继续优化，用一维数组实现。注意遍历的顺序是从右到左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

intdp[C+1];


intksi(intn, intC) {

    for(int i = 1; i <= n; i++)

      for(int j = C; j >= c[i]; j--)

          dp[j] = max(dp[j], dp[j-c[i]] + v[i]);


    returndp[C];

}

通过滚动数组，可以将空间复杂度从 \(O(nC)\) 优化到 \(O(C)\)。

几点注意事项：

  1. 确定 dp 数组的含义
  1. 找到状态转移方程
  1. 找到递推的起始状态，即初始化 dp 数组
  1. 优化 dp 数组空间

完全背包

题目描述 给定有 \(n\) 种物品和一个容量为 \(C\) 的背包，每种物品都有无限件可用。第 \(i\) 种物品的体积是 \(c_i\) ，价值是 \(v_i\)。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

基本思路 这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。这时候每种物品取值 \(k \notin \{0,1\}\)，而是 \(k \in \{0, 1, \cdots, j/c[i]\}\)。如果仍然按照解 01 背包时的思路，那么转移方程

\[ dp[i][j] = \max\{dp[i-1][j], dp[i-1][j-k*c[i]] + k*v[i]\}, k \in \{0, 1, \cdots, j/c[i]\} \]

时间复杂度是 \(O(nC\sum C/c_i)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

intksi(intn, intC)

{

  for(int i = 1 ; i<= n; i++)

    for(int j = 1 ; j <= C; j++)

      for(int k = 0 ; k*c[i] <= j ; k++)

        dp[i][j] = max(dp[i][j], dp[i-1][j-k*c[i]] + k*v[i]);


  returndp[n][C];

}

优化思路 一种启发式优化方法是：若两件物品 \(i\)，\(j\)，满足 \(c[i] \ge c[j]\)，且 \(v[i] \le v[j]\)，则将物品 \(i\) 去掉，不用考虑。这个优化的正确性显然：更漂亮更聪明的物品总是好的。对于理想情况，可以排除很多不需要考虑的物品，但是最坏情况并不能排除。即漂亮的不聪明，聪明的又不漂亮。

二进制拆分优化 考虑一下，若背包容量最多可以放入 \(\left\lfloor C / c_i\right\rfloor\) 个物品 \(i\)，假如有 7 个，理论上我们需要分别考虑加入 \(k=0,1,2\cdots7\) 个的情况。如果把 7 个物品拆分为，重量为 \(c_i, 2c_i, 4c_i\)，对应的价值是\(v_i, 2v_i, 4v_i\)，这新的三个物品的组合可以表示原来的 7 个物品。一般地，把第 \(i\) 种物品拆成容量为 \(c_i2^k\)、价值为 \(v_i2^k\) 的若干件物品，其中 \(k\) 取遍满足 \(c_i2^k ≤ C\) 的非负整数。复杂度可以降为 \(O(C\sum\log(C/c_i)\)。

\(O(NC)\) 的算法 考虑 01 背包中的转移方程

\[ dp[i][j] = \max\{dp[i-1][j], {\color{red}{}dp[i-1][j-c[i]]} + v[i]\} \]

只需要修改为

\[ dp[i][j] = \max\{dp[i-1][j], {\color{red}{}dp[i][j-c[i]]} + v[i]\} \]

因为每件物品是无限多种，所以在考虑“加选一件第 \(i\) 种物品”这种策略时，却正需要一个可能已选入第 \(i\) 种物品的子结果 \(dp[i][j-c[i]]\)。空间优化时可以简化为（用纸笔模拟一遍即可明白其中的道理。）

\[ dp[j] = \max\{dp[j], {\color{red}{}dp[j-c[i]]} + v[i]\} \]

和 01 背包不同的是，遍历时要从左到右遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

intcks(intn, intC) {

    for(int i = 1; i <= n; i++)

      for(int j = c[i]; j <= C; j--)

          dp[j] = max(dp[j], dp[j-c[i]] + v[i]);


    returndp[C];

}

多重背包

题目描述 给定有 \(n\) 种物品和一个容量为 \(C\) 的背包。第 \(i\) 种物品的体积是 \(c_i\) ，价值是 \(v_i\)，有 \(m_i\) 个。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

基本思路 和完全背包类似，这是需要考虑 \(k = 1, 2, \cdots, m_i\)，总的时间复杂度是 \(O(C\sum m_i)\)。

\[ dp[i][j] = \max\{dp[i-1][v-kc_i] + kv_i) \mid0\le k \le m_i\} \]

二进制拆分 仍然考虑二进制的思想，考虑把第 i 种物品换成若干件物品，使得原问题中第 i 种物品可取的每种策略（取 \(0\cdots m_i\) 件）均能等价于取若干件代换以后的物品。另外，取超过 \(m_i\) 件的策略必不能出现。将第 \(i\) 种物品分成若干件 01 背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为 \(1, 2, 2^2, \cdots, 2^{k−1}, m_i − 2^{k + 1}\)，且 \(k\) 是满足 \(m_i − 2^{k + 1} > 0\) 的最大整数。例如，如果 \(m_i\) 为 13，则相应的 \(k = 3\)，这种最多取 \(13\) 件的物品应被分成系数分别为 \(1, 2, 4, 6\) 的四件物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

intksb(intn, intC) {

  intnc[n * 10];

  intnv[n * 10];

  int nn = 0;


  // 二进制拆分

  for (int i = 0; i < n; i++) {

    int num = m[i];

    for(int k = 1; k <= num; num -= k, k*=2) {

      nc[nn] = c[i] * k;

      nv[nn++] = v[i] * k;

    }

    if (num > 0) {

      nc[nn] = c[i] * num;

      nv[nn++] = v[i] * num;

    }

  }


  // 0/1 背包求解

  for (int i = 0; i < nn; i++)

    for (int j = C; j >= nc[i]; j--)

      dp[j] = max(dp[j], dp[j-c[i]] + v[i]);



  returndp[C];

}


通过单调队列优化，可以 \(O(nC)\) 实现分组背包。

编辑距离

问题背景 编辑距离,也叫莱文斯坦距离(Levenshtein)，在计算语言学和计算机科学中，编辑距离是一个字符串度量，即一种量化两个字符串(如单词)之间的差异性的方法，通过计算将一个字符串转换为另一个字符串所需的最小操作数来测量。编辑距离可以应用自然语言处理中，比如自动拼写纠正，如果你拼写错了一个单词，那么可以从字典中选择与错误单词的编辑距离最近的单词作为纠正的候选单词。在生物信息学中，DNA 序列可以看作是字母 A、C、G 和 T 的字符串，编辑距离则可以用来量化 DNA 序列的相似性。

问题描述 给定两个字符串 a 和 b，计算将字符串 a 转换为字符串 b 所需要的最少操作。这里的操作是指对字符串 a 执行以下三种：

  1. 删除一个字符；
  2. 插入一个字符；
  3. 替换一个字符。

例如，a = "sunday"，b = "saturday，这两个字符串第一个和最后三个是相同的，那么只需要将 "un" 转换为 "atur"。这需要三个操作：1）n 替换为 r 变成 ur，2）插入 t 变成 tur，3）插入 a 变成 atur。

基本思路 最简单的思路是从最后一个字符（也可以从第一个字符）枚举所有的可能性。采用递归的方法。令 m = a.length(), n = b.length()，函数 edit_dist(a, b, m, n) 返回将 a 转换为 b 所需要的最少操作数。

  1. 如果最后一个字符相同 a[m-1] == b[n-1]，那么不需要考虑最后一个字符，直接处理前一个字符就可以了，即转换为 edit_dist(a, b, m-1, n-1)。

  2. 如果最后一个字符不相同，那么可以通过三个操作来使它们相同。

    1. 删除一个字符，a 少一个，b 不变，edit_dist(a, b, m-1, n) + 1;

    2. 插入一个字符，a 不变，b 少一个（因为已经插入一个和 b 相同的），edit_dist(a, b, m, n-1) + 1；

    3. 替换一个字符，a 和 b 同时少一个，edit_dist(a, b, m-1, n-1) + 1。

进一步考虑可以发现，【1】 和 【2.c】两种情况可以合并为 edit_dist(a, b, m-1, n-1) + a[m-1] != b[m-1]。

边界情况，1）如果 a 为空字符串，那么至少需要插入 n 个字符变成 b；2）如果 b 为空字符串，那么至少需要删除 m 个字符变成 b。

下面是递归的实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


intmin(intx, inty, intz) { returnmin(min(x, y), z); }


intedit_dist(string&a, string&b, intm, intn)

{

  if (m == 0) return n;


  if (n == 0) return m;


  returnmin(edit_dist(a, b, m-1, n) + 1, // remove

             edit_dist(a, b, m, n-1) + 1, // insert

             edit_dist(a, b, m-1, n-1) + (a[m-1] == b[m-1]) // replace

            );

}

上述算法每一步都需要考虑三种情况，时间复杂度 \(O(3^{\max(m, n)})\)，空间复杂度 \(O(\max(m,n))\)。

优化方法 仔细分析可以发现，递归过程中会重复计算很多相同的情况，所以只需要加上记忆化即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

dp[M+1][N+1] = {0};


intmin(intx, inty, intz) { returnmin(min(x, y), z); }


intedit_dist(string&a, string&b, intm, intn)

{


  if(dp[m][n]) returndp[m][n];


  if (m == 0)  returndp[m][n] = n;


  if (n == 0)  returndp[m][n] = m;


  returndp[m][n] = min(edit_dist(a, b, m-1, n) + 1, // remove

                        edit_dist(a, b, m, n-1) + 1, // insert

                        edit_dist(a, b, m-1, n-1) + (a[m-1] != b[n-1]) // replace

                       );

}

也可以写成递推形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

dp[M+1][N+1] = {0};


intmin(intx, inty, intz) { returnmin(min(x, y), z); }


intedit_dist(string&a, string&b)

{

  int m = a.length(), n = b.length();



  for(int i = 1; i <= m; i++) {

    dp[i][0] = i;

    for(int j = 1; j <= n; j++) {

      dp[0][j] = j;

      dp[i][j] = min(dp[i-1][j] + 1,

                     dp[i][j-1] + 1,

                     dp[i-1][j-1] + (a[i-1] != b[j-1])

                    );

    }

  }

  returndp[m][n];

}

优化后时间复杂度和空间度都是 \(O(mn)\)。

因为每一次计算仅与前一行和当前行有关系，所以可以进一步采用交替滚动数组将空间复杂度优化到 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

dp[2][N+1] = {0};


intmin(intx, inty, intz) { returnmin(min(x, y), z); }


intedit_dist(string&a, string&b)

{

    int m = a.length(), n = b.length();

    int pre = 0, cur = 1;



    //init pre row

    for(int j = 1; j <= n; j++)

      dp[pre][j] = j;



    for(int i = 1; i <= m; i++) {

      dp[cur][0] = i;

      for(int j = 1; j <= n; j++) {

        dp[cur][j] = min(dp[pre][j] + 1,

                         dp[cur][j-1] + 1,

                         dp[pre][j-1] + (a[i-1] != b[j-1])

                      );

      }

      swap(pre, cur);

  }

  returndp[pre][n];

}

最长公共子序列(Longest Common Subsequence)

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

问题描述 给定两个字符串 a 和 b，计算这两个字符串的最长公共子序列的长度。如果不存在公共子序列，则长度为 0。

基本思路 这个问题和【编辑距离】问题类似，只不过只有一个 删除 操作。令 \(dp[i][j]\) 表示表示字符串 a[1...i] 和字符串 b[1...j] 的最长公共子序列，那么 \(dp[m][n]\) 就是 a 和 b 的最长公共子序列。

问题分为两种情况：

  1. 当 \(a[i] = b[j]\)，那么最长公共子序列的长度可以加 1，即 \(dp[i][j] = dp[i-1][j-1] + 1\)。
  2. 当 \(a[i] \ne b[j]\)，这时有两种选择，删除 \(a[i]\) 或者删除 \(b[j]\)，选择最大的情况，即 \(dp[i][j] = max(dp[i-1][j], dp[i][j-1])\)。（能不能同时删除？）

边界条件，如果有一个字符串为空，那么显然没有公共子序列，直接返回 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

dp[2][N+1] = {0};


intmin(intx, inty, intz) { returnmin(min(x, y), z); }


intlcs(string&a, string&b)

{

  int m = a.length(), n = b.length();

  int pre = 0, cur = 1;



  for(int i = 1; i <= m; i++) {

    for(int j = 1; j <= n; j++) {

      if(a[i-1] == b[j-1])

        dp[cur][j] = dp[pre][j-1] + 1;

      else

        dp[cur][j] = max(dp[cur][j-1], dp[pre][j]);

    }

    swap(pre, cur);

  }

  returndp[pre][n];

}

数位 DP