动态规划 Dynamic Programming

基本算法思想系列文章链接：

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

一个模型

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

三个特征

最优子结构: 问题的最优解包含子问题的最优解
- 我们可以通过子问题的最优解，推导出问题的最优解。
- 对应到动态规划问题模型上，可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来
无后效性
- 第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。
- 第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。
重复子问题
- 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

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

假设我们有一个 n 乘以 n 的矩阵 w[n][n]。

矩阵存储的都是正整数

   0 1 2 3
0 |1|3|5|9|
1 |2|1|3|4|
2 |5|2|6|7|
3 |6|8|4|3|

棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。

每次只能向右或者向下移动一位。
从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。
那从左上角移动到右下角的最短路径长度是多少呢？

这个问题是否符合“一个模型”？

从 (0, 0) 走到 (n-1, n-1)，总共要走 2*(n-1) 步，也就对应着 2*(n-1) 个阶段。
每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。
定义状态的时候，我们把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)
所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

这个问题是否符合“三个特征”？

先用回溯算法来编写代码，再画一下递归树，就会发现，递归树中有重复的节点。说明这个问题中存在重复子问题。
如果我们走到 (i, j) 这个位置，我们只能通过 (i-1, j)，(i, j-1) 这两个位置移动过来，也就是说，我们想要计算 (i, j) 位置对应的状态，只需要关心 (i-1, j)，(i, j-1) 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，我们仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。
因为我们只能往右或往下移动，所以，我们只有可能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。换句话说就是，min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来。这就说明，这个问题符合“最优子结构”。 min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

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

1. 状态转移表法

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。

当我们拿到问题的时候，我们可以先用简单的回溯算法解决，

func main() {
    minDistBT(0, 0, 0, "", [][]int{
        {1, 3, 5, 9},
        {2, 1, 3, 4},
        {5, 2, 6, 7},
        {6, 8, 4, 3},
    }, 4)
    println(minDist)
}

var minDist = math.MaxInt32

// 调用方式: minDistBacktracing(0, 0, 0, w, n);
func minDistBT(i, j, dist int, x string, w [][]int, n int) {
        dist += w[i][j]
        //到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
        if i == n-1 && j == n-1 {
            if dist < minDist {
                minDist = dist
                println(i, j, dist, fmt.Sprintf("%s,%d",x, w[i][j]))
            }
            return
        }
        if i < n-1 { // 往下走，更新i=i+1, j=j
            minDistBT(i+1, j, dist, fmt.Sprintf("%s,%d", x, w[i][j]), w, n)
        }
        if j < n-1 { // 往右走，更新i=i, j=j+1
            minDistBT(i, j+1, dist, fmt.Sprintf("%s,%d", x, w[i][j]), w, n)
        }
}

然后定义状态，每个状态表示一个节点，然后对应画出递归树。

在递归树中，一个状态（也就是一个节点）包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。
从图中，我们看出，尽管 (i, j, dist) 不存在重复的，但是 (i, j) 重复的有很多。
对于 (i, j) 重复的节点，我们只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了。
                                   f(0,0,1)
                              往下/     \往右  
                 f(1,0,3)                               f(0,1,4)
            往下/     \往右                         往下/     \往右
      f(2,0,8)            f(1,1,4)          f(1,1,5)          f(0,2,9)
 往下/     \往右      往下/     \往右    往下/     \往右    往下/     \往右
f(3,0,14) f(2,1,10) f(2,1,6) f(1,2,7) f(2,1,7) f(1,2,8) f(1,2,11) f(0,3,18)
  /\         /\        /\       /\       /\       /\       /\        /\
  ...        ...       ...      ...      ...      ...      ...       ...

从递归树中，我们很容易可以看出来，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。
- 找到重复子问题之后，接下来，我们有两种处理思路，第一种是直接用回溯加“备忘录”的方法，来避免重复子问题。
- 第二种是使用动态规划的解决方法，状态转移表法。

状态转移表法

先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。
- 每个状态包含三个变量，行、列、数组值。
根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。
最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。
如果问题的状态比较复杂，需要很多变量来表示，那对应的状态表可能就是高维的，那这个时候，我们就不适合用状态转移表法来解决了

表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。
我们按照决策过程，通过不断状态递推演进，将状态表填好。
为了方便代码实现，我们按行来进行依次填充。

初始化(第0行,第0列)    第1行
    +3 +5 +9
   +--+--+--+--+     +--+--+--+--+
+2 |1 |4 |9 |18|     |1 |4 |9 |18|
+5 |3 |  |  |  |     |3 |4 |7 |11| 4=min(3+1,4+1)
+6 |8 |  |  |  |     |8 |  |  |  | 7=min(4+3,9+3)
   |14|  |  |  |     |14|  |  |  | 11=min(7+4,18+4)
   +--+--+--+--+     +--+--+--+--+

    第2行             第3行
   +--+--+--+--+     +--+--+--+--+
   |1 |4 |9 |18|     |1 |4 |9 |18|
   |3 |4 |7 |11|     |3 |4 |7 |11|
   |8 |6 |12|18|     |8 |6 |12|18|
   |14|  |  |  |     |14|14|16|19|
   +--+--+--+--+     +--+--+--+--+

弄懂了填表的过程，代码实现就简单多了。我们将上面的过程，翻译成代码，就是下面这个样子。

func main() {
        println(minDistDP([][]int{
                {1,3,5,9},
                {2,1,3,4},
                {5,2,6,7},
                {6,8,4,3},
        }, 4))
}

func minDistDP(matrix [][]int, n int) int {
        states := make([][]int, n)
        for i := range states {
                states[i] = make([]int, n)
        }

        sum := 0
        for j := 0; j < n; j++ {
                sum += matrix[0][j]
                states[0][j] = sum
        }
        sum = 0
        for i := 0; i < n; i++ {
                sum += matrix[i][0]
                states[i][0] = sum
        }
        for i:=1; i<n; i++ {
                for j:=1; j<n; j++ {
                        states[i][j] = matrix[i][j] + (int)(math.Min(float64(states[i][j-1]), float64(states[i-1][j])))
                }
        }
        return states[n-1][n-1]
}

2. 状态转移方程法

根据最优子结构，写出递归公式，也就是所谓的状态转移方程(min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j)))。
有了状态转移方程，一般使用这两种方法来实现代码：

递归加“备忘录”

func main() {
    println(minDist(n-1,n-1))
}
var matrix = [][]int{
    {1,3,5,9},
    {2,1,3,4},
    {5,2,6,7},
    {6,8,4,3},
}
var n =4
var mem [4][4]int
func minDist(i,j int) int {  // 调用minDist(n-1, n-1)
    if i == 0 && j == 0 { return matrix[0][0] }
    if mem[i][j] > 0 { return mem[i][j] }
    minLeft := math.MaxInt32
    if j-1 >= 0 {
        minLeft = minDist(i, j-1)
    }
    minUp := math.MaxInt32
    if i-1 >= 0 {
        minUp = minDist(i-1, j)
    }
    currMinDist := matrix[i][j] + int(math.Min(float64(minLeft), float64(minUp)))
    mem[i][j] = currMinDist
    return currMinDist
}

迭代递推：跟状态转移表法的代码实现是一样的，只是思路不同。

0-1背包

我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码

回溯算法实现：

func main() {
    f(0, 0)
    println(maxW)
}

var (
    maxW = math.MinInt32
    weight = []int{2, 2, 4, 6, 3} // 物品重量
    n =5  // 物品个数
    w = 9  // 背包承受的最大重量
)

func f(i, cw int) { // 调用f(0, 0)
    if cw == w || i == n { // cw==w表示装满了，i==n表示物品都考察完了
        if cw > maxW { maxW = cw }
        return
    }
    f(i+1, cw)  // 选择不装第i个物品
    if cw + weight[i] <= w {
        f(i+1, cw + weight[i])  // 选择装第i个物品
    }
}

递归树中的每个节点表示一种状态，我们用（i, cw）来表示。其中，i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量。

画递归树，找重复子问题：

                          f(0,0)
                        /       \
            f(1,0)                     f(1,2)
           /     \                    /      \
     f(2,0)       f(2,2)        f(2,2)        f(2,4)
     / \           / \           / \           / \
f(3,0) f(3,4) f(3,2) f(3,6) f(3,2) f(3,6) f(3,4) f(3,8)
 /\      /\     /\      /\     /\     /\     /\     /\
 ..      ..     ..      ..     ..     ..     ..     ..

画状态转移表，根据递推关系填表我们把整个求解过程分为n个阶段(层)，每个阶段会决策一个物品是否放到背包中，不同的决策会生成不同的状态。我们把每一层重复的状态（节点）合并，只记录不同的状态(每一层不同状态的个数都不会超过 w 个)，然后基于上一层的状态集合，来推导下一层的状态集合。

我们用一个二维数组states[n][w+1]来记录每层可以达到的不同状态。
  初始状态                         第0个物品决策完之后
      0 1 2 3 4 5 6 7 8 9              0 1 2 3 4 5 6 7 8 9
     +-+-+-+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+-+-+-+
w=2 0|0 0 0 0 0 0 0 0 0 0|       w=2 0|1 0 1 0 0 0 0 0 0 0|
w=2 1|0 0 0 0 0 0 0 0 0 0|       w=2 1|0 0 0 0 0 0 0 0 0 0|
w=4 2|0 0 0 0 0 0 0 0 0 0|       w=4 2|0 0 0 0 0 0 0 0 0 0|
w=6 3|0 0 0 0 0 0 0 0 0 0|       w=6 3|0 0 0 0 0 0 0 0 0 0|
w=3 4|0 0 0 0 0 0 0 0 0 0|       w=3 4|0 0 0 0 0 0 0 0 0 0|
     +-+-+-+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+-+-+-+

  第1个物品决策完之后               第2个物品决策完之后
      0 1 2 3 4 5 6 7 8 9              0 1 2 3 4 5 6 7 8 9
     +-+-+-+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+-+-+-+
w=2 0|1 0 1 0 0 0 0 0 0 0|       w=2 0|1 0 1 0 0 0 0 0 0 0|
w=2 1|1 0 1 0 1 0 0 0 0 0|       w=2 1|1 0 1 0 1 0 0 0 0 0|
w=4 2|0 0 0 0 0 0 0 0 0 0|       w=4 2|1 0 1 0 1 0 1 0 1 0|
w=6 3|0 0 0 0 0 0 0 0 0 0|       w=6 3|0 0 0 0 0 0 0 0 0 0|
w=3 4|0 0 0 0 0 0 0 0 0 0|       w=3 4|0 0 0 0 0 0 0 0 0 0|
     +-+-+-+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+-+-+-+

  第3个物品决策完之后               第4个物品决策完之后
      0 1 2 3 4 5 6 7 8 9              0 1 2 3 4 5 6 7 8 9
     +-+-+-+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+-+-+-+
w=2 0|1 0 1 0 0 0 0 0 0 0|       w=2 0|1 0 1 0 0 0 0 0 0 0|
w=2 1|1 0 1 0 1 0 0 0 0 0|       w=2 1|1 0 1 0 1 0 0 0 0 0|
w=4 2|1 0 1 0 1 0 1 0 1 0|       w=4 2|1 0 1 0 1 0 1 0 1 0|
w=6 3|1 0 1 0 1 0 1 0 1 0|       w=6 3|1 0 1 0 1 0 1 0 1 0|
w=3 4|0 0 0 0 0 0 0 0 0 0|       w=3 4|1 0 1 1 1 1 1 1 1 1|
     +-+-+-+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+-+-+-+
考察完所有物品后，只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值

将填表过程翻译成代码

func main() {
    println(knapsack([]int{2,2,4,6,3}, 5, 9))
}

func knapsack(weight []int, n, w int) int {
    states := make([][]bool, n)
    for i := range states {
        states[i] = make([]bool, w+1)
    }
    states[0][0] = true   // 第一行的数据要特殊处理，可以利用哨兵优化
    if weight[0] <= w {
        states[0][weight[0]] = true
    }
    for i:=1; i<n; i++ { // 动态规划状态转移
        for j:=0; j<=w; j++ { // 不把第i个物品放入背包
            if states[i-1][j] { states[i][j] = states[i-1][j] }
        }
        for j:=0; j<=w-weight[i]; j++ {
            if states[i-1][j] { states[i][j+weight[i]] = true }
        }
    }
    for i:=w; i>=0; i-- { // 输出结果
        if states[n-1][i] { return i }
    }
    return 0
}

如何实现搜索引擎中的拼写纠错功能

回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码

专题: 基本算法思想

本文发表于 2021-07-07，最后修改于 2021-07-07。

本站永久域名「 jiavvc.top 」，也可搜索「后浪笔记一零二四」找到我。

上一篇 « 回溯算法下一篇 » 时间复杂度分析