zdaiot

404NotFound

40动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

发表于 分类于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

本节主要涉及动态规划的一些理论知识。你需要解决这几个问题：什么样的问题可以用动态规划解决？解决动态规划问题的一般思考过程是什么样的？贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系？

“一个模型三个特征”理论讲解

什么样的问题适合用动态规划来做，其实这有一套成熟的理论，叫作”一个模型三个特征“理论。

一个模型理论指的是动态规划适合解决的问题的模型。这个模型可以定义为”多阶段决策最优解模型“。我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段，每个决策阶段都对应着一组状态。然后需要寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

”三个特征“分别为最优子结构、无后效性和重复子问题。下面对这三个概念详细解释一下。

最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，可以通过子问题的最优解，推导出问题的最优解。

若把最优子结构对应到前面定义的动态规划问题模型上，可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

“一个模型三个特征”实例剖析

假设有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？

img

首先，看看这个问题是否符合一个模型？从 (0, 0) 走到 (n-1, n-1)，总共要走 2*(n-1) 步，也就对应着 2*(n-1) 个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。

我们把状态定义为 min_dist(i, j)，其中 i 表示行，j 表示列。min_dist 表达式的值表示从 (0, 0) 到达 (i, j) 的最短路径长度。所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

img

接着看，这个问题是否符合”三个特征“？

若用回溯算法解决这个问题，并画出递归树。从中可以发现，递归树中有重复的节点。重复的节点表示，从左上角到节点对应的位置，有多种路线，这也能说明这个问题中存在重复子问题。如下图所示，有很多种路径可以从左上角 (0, 0) 走到下面的 (3, 3) 位置，对于这很多种路径来说，接下来的情况就完全一致了，也就是包含了重复子问题。

img

当走到 (i, j) 这个位置时，只能通过 (i-1, j)，(i, j-1) 这两个位置移动过来。也就是说，要计算 (i,j) 位置对应的状态，只需要关心 (i-1, j)，(i, j-1) 这两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，我们仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。

前面定义从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)。因为只能往右或往下移动，所以只有可能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。即到达 (i, j) 的最短路径要么经过 (i, j-1)，要么经过 (i-1, j)，而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是，min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来。这就说明，这个问题符合“最优子结构”。

1
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

两种动态规划解题思路总结

解决动态规划问题，一般有两种思路。分别为状态转移表法和状态转移方程法。

状态转移表法

能用动态规划解决的问题，都可以用回溯算法的暴力搜索解决。拿到问题时，可以先用简单的回溯算法解决，定义状态，每个状态表示一个节点，然后对应画出递归树。从递归树中，很容易观察出，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。

找到重复子问题之后，会有两种处理思路。第一种是直接用回溯加“备忘录”的方法，来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法，状态转移表法。

对于第二种思路，先画出一个状态表。状态表一般都是二维的，可以想象成一个二维数组。其中，每个状态包含三个变量，行、列、数组值。然后，根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，将这个递推填表的过程，翻译成代码，就是动态规划代码了。

但是若问题的状态比较复杂，需要很多变量来表示，那对应的状态表可能就是高维的，而不是二维的。这时，就不适合使用状态转移表法来解决了。一方面是因为高维状态转移表不好画图表示，另一方面是因为人脑确实很不擅长思考高维的东西。

现在尝试使用状态转移表法，解决之前那个矩形最短路径的问题。从起点到终点，有很多种不同的走法。我们可穷举所有走法，然后对比找出一个最短走法。这个过程，可以利用回溯算法这个比较有规律的穷举算法，做到无重复又不遗漏地穷举所有走法。对一个的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量
// 调用方式：minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
  // 到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
  if (i == n && j == n) {
    if (dist < minDist) minDist = dist;
    return;
  }
  if (i < n) { // 往下走，更新i=i+1, j=j
    minDistBT(i + 1, j, dist+w[i][j], w, n);
  }
  if (j < n) { // 往右走，更新i=i, j=j+1
    minDistBT(i, j+1, dist+w[i][j], w, n);
  }
}

接着画出递归树来寻找重复子问题。在递归树中，一个状态（也就是一个节点）包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。如下图，可以看出尽管 (i, j, dist) 不存在重复的，但是 (i, j) 重复的有很多。对于 (i, j) 重复的节点，只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了。

img

既然存在重复子问题，那么能否使用动态规划解决这个问题呢？首先，画出一个二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。按照决策过程，通过不断状态递推演进，将状态表填好。为了方便代码实现，我们按行来进行依次填充。

img

img

对应的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minDistDP(int[][] matrix, int n) {
  int[][] states = new int[n][n];
  int sum = 0;
  for (int j = 0; j < n; ++j) { // 初始化states的第一行数据
    sum += matrix[0][j];
    states[0][j] = sum;
  }
  sum = 0;
  for (int i = 0; i < n; ++i) { // 初始化states的第一列数据
    sum += matrix[i][0];
    states[i][0] = sum;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < n; ++j) {
      states[i][j] = 
            matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
    }
  }
  return states[n-1][n-1];
}

状态转移方程法

状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。一般情况下，我们有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。

上面例子的最优子结构，也就是状态转移方程写下来如下所示。需要注意的是，状态转移方程是解决动态规划的关键。

1
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

下面用递归加“备忘录”的方式，将状态转移方程翻译成代码，如下所示。对于另一种实现方式，跟状态转移表法的代码实现是一样的，只是思路不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int[][] matrix = 
         {{1，3，5，9}, {2，1，3，4}，{5，2，6，7}，{6，8，4，3}};
private int n = 4;
// 备忘录
private int[][] mem = new int[4][4];
public int minDist(int i, int j) { // 调用minDist(n-1, n-1);
  if (i == 0 && j == 0) return matrix[0][0];
  if (mem[i][j] > 0) return mem[i][j];
  int minLeft = Integer.MAX_VALUE;
  if (j-1 >= 0) {
    minLeft = minDist(i, j-1);
  }
  int minUp = Integer.MAX_VALUE;
  if (i-1 >= 0) {
    minUp = minDist(i-1, j);
  }
  
  int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
  mem[i][j] = currMinDist;
  return currMinDist;
}

四种算法思想比较分析

下面我们分析下已经学过的四种算法思想——贪心、分治、回溯和动态规划，看它们之间有什么区别和联系。

若将这四种算法思想分一下类，那么贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类。因为前三个算法解决问题的模型，都可以抽象成本节的多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

内容小结

本节首先讲了什么样的问题适合用动态规划解决。这些问题可以总结概括为“一个模型三个特征”。其中，“一个模型”指的是，问题可以抽象成分阶段决策最优解模型。“三个特征”指的是最优子结构、无后效性和重复子问题。

接着，本节讲了动态规划的两种解题思路，分别是状态转移表法和状态转移方程法。其中，状态转移表法解题思路大致可以概括为，回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。状态转移方程法的大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。

最后，本节对比了之前讲过的四种算法思想。贪心、回溯、动态规划可以解决的问题模型类似，都可以抽象成多阶段决策最优解模型。尽管分治算法也能解决最优问题，但是大部分问题的背景都不适合抽象成多阶段决策模型。

课后思考

假设我们有几种不同币值的硬币 v1，v2，……，vn（单位是元）。如果我们要支付 w 元，求最少需要多少个硬币。比如，我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，最少需要 3 个硬币（3 个 3 元的硬币）。

答：动态规划状态转移表解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int minCoins(int money) {
  if (money == 1 || money == 3 || money == 5) return 1;
  // 最多需要money个硬币，而不同个硬币组成的价值在0到money之间，由此解释下面 state的大小
  boolean [][] state = new boolean[money][money + 1];
  if (money >= 1) state[0][1] = true;
  if (money >= 3) state[0][3] = true;
  if (money >= 5) state[0][5] = true;
  for (int i = 1; i < money; i++) {
    for (int j = 1; j <= money; j++) {
      if (state[i - 1][j]) {
        if (j + 1 <= money) state[i][j + 1] = true;
        if (j + 3 <= money) state[i][j + 3] = true;
        if (j + 5 <= money) state[i][j + 5] = true;
        if (state[i][money]) return i + 1; // 找到了，停止
      }
    }
  }
  return money;
}
------ 本文结束------
坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道