看完就懂系列—动态规划

动态规划的主要思想

• 将原问题分解为更简单的子问题 （重要的事情默念三遍），通过解决子问题来解决原问题。
• 记忆化搜索 (存储子问题的解，解决重叠子问题多次计算的问题)。

动态规划的三要素:

• 最优子结构：原问题最优解所包含的子问题都是最优的（子问题的最优解能组合成原问题的最优解）则该子问题为原问题的最优子结构。
• 状态转移方程：表示前后阶段关系的方程（原问题与子问题的关系方程）。
• 边界：无需继续分解，可以直接得到值的问题（没有边界的问题是无解的）。

这里概括了一下动态规划的主要思想和要素，让我们暂时带着疑问，先来看几个经典问题。

动态规划经典问题

书架放法问题

假设有一个书架，最多容纳10本书。现在我们要把这个书架放满，条件是，每次只能放1本或者2本。问：放满十本书总共有多少种放法?

下图为其中一种方法：每次只放1本。我们可以表示为1,1,1,1,1,1,1,1,1,1

下图为其中另外一种方法：每次只放2本。我们可以表示为2,2,2,2,2

显然上面的这两种放法都是最简单的放法，总放法远远不止这两种。还记得我们默念的那一句吗，我们现在就想这个复杂的问题能不能分解成更简单的子问题。

我们反过来想一下，放满10本书之前书架的状态是怎么样的？在放满10本书之前：

• 书架已经放了9本（最后一次放1本）
• 书架已经放了8本（最后一次放2本）

因此书架放10本书的总放法数，等同于书架放9本书的总放法数 + 书架放8本书的总放法数。 设F(x)的解为书架放满x本书的总放法数 ，可以得到一个方程 F(x) = F(x-1) + F(x-2)，(x>1)，这个方程就是状态转移方程 。原问题就可以分解成：F(10) = F(9) + F(8)， F(9)和F(8)为F(10)的最优子结构 。 得到这个方程后，我们很容易就可以得到这个问题的解了，这不就是典型的递归问题嘛。

递归求解

const bookrackRecur = (window.tempF = (bookrack) => {
    if (bookrack < 3) {
        return bookrack;
    }
    //根据状态转移方程F(x) = F(x-1) + F(x-2)
    return window.tempF(bookrack - 1) + window.tempF(bookrack - 2);
})(10);
console.log(bookrackRecur); //89
复制代码

分解问题的思想让我们很容易就知道了解题的思路，但是上面递归的解法有一种问题。会重复计算相同问题。

如图可以看到原问题分解成子问题时，会出现很多 重叠子问题 ，因此用递归自顶向下求解时，会重复求解一些问题，这个算法的时间复杂度是 O(2^n) 。那么怎么去优化这个算法呢？现在我们就可以用动态规划了。上文说了动态规划的另外一个主要思想是 记忆化搜索

，我们把之前问题的解存储下来，那么在求解过程中遇到相同问题时，就可以直接得到值了。

动态规划求解

下面我们转变下思路，尝试着自底向上迭代求解。下面借助一张表来说明，F(x)同样表示为书架放满x本书的总放法。

x	0	1	2	3	...
F(x)	0	1	2	3 (F(2)+F(1))	...

该问题具有 边界：

• F(1)，只放1本书在书架上的放法只有一种：1。
• F(2)，放2本书在书架上的方法有两种：1,1和2。

根据状态转移方程，我们知道F(3)是只依赖F(1)和F(2)的，我们在程序中保存了前两个问题的解，就可以得到目前问题的解。

const bookrackDP = ((bookrack) => {
    //为了问题更好的对应数组下标，加入问题0, F(0) = 0
    //保存前两个问题的解F(1) = 1, F(2) = 2;
    let record = [0, 1, 2];
    for (let i = 0; i <= bookrack; i++) {
        if (i >= 3) {
            //记录问题的解
            record[i] = record[i - 1] + record[i - 2];
        }
    }
    //根据记录直接得到问题的解
    return record[bookrack];
})(10);
console.log(bookrackDP);
复制代码

这种算法的时间复杂度为O(n)。上面的代码用了数组存储子问题的解，其实是可以再优化一下的。我们上面分析了，目前问题的解只依赖于前两个问题，因此用两个局部变量存储前两个问题的解就行了，这里就不再展示代码了。我们看一个复杂点的问题。

01背包问题

假设有一个运气爆棚的猎人进入到了彩虹洞中，地精让这个人从宝库中任意拿走物品，直到猎人的背包装不下为止。宝库中每个物品都有特定的价值和重量，猎人的背包承重有限。那么问题来了，猎人怎么装物品才能获得最大价值呢？假设猎人背包最大承重为20公斤，物品重量及价值如下图：

思路：这是一个多阶段的决策问题，每一阶段的决策都会影响到下一阶段的决策（装了物品1，可能就会装不了物品2...）。还是按照分解问题的思想来，得到解题思路再说。我们先用方程来普适化表示这一问题： 假设F(i, c)的解为，从i件物品中，挑选一些物品放入剩余容量为c（capacity）的背包中，使的背包物品价值最大

。因此原问题可以表示为：F(5, 20)。思考一下，怎么将F(5, 20)分解呢？

选与不选神器

我们可以考虑面对物品5时， 选不选 的问题。(这个地方着重理解)

1. 首先背包剩余容量必须大于物品5的重量，否则根本放不下，放不下相当于不用考虑物品5，原问题的解等同于 从前4件物品中，挑选一些物品放入背包中（目前背包什么都没装），背包物品总价值最大 。表示为：F(4, 20)。
2. 选了物品5，问题的解为， 选了物品5了，背包价值为物品5的价值，再从前4件物品中，挑选一些物品放入背包中（目前背包已装物品5） ，背包物品总价值最大。方程表示为F(4, 20 - 物品5重量) + 物品5价值 = F(4, 16) + 5。
3. 不选物品5，等同于不考虑物品5，问题的解为， 从前4件物品中，挑选一些物品放入背包中（目前背包什么都没装） ，背包物品总价值最大。表示为：F(4, 20)。
4. 到底选还是不选，判断选和不选的情况中，哪种情况的背包总价值高，选价值高的情况。max(F(4, 16) + 5, F(4, 20))

根据上面的分析我们就可以得到这个问题的 状态转移方程 了（同样的我们发现可能会有重叠子问题）：

F(i, c) = max(F(i-1, c-weights[i]) + values[i] , F(i-1, c))， （i > 0）

很容易就可以得到递归的解法了

递归解法

let goods = [
    {value: 0, weight: 0}, //方便对应下标
    {value: 3, weight: 2},
    {value: 4, weight: 3},
    {value: 8, weight: 5},
    {value: 10, weight: 9},
    {value: 5, weight: 4}
];

const knapsackRecur = ((goods, capacity) => {
    let recurF = (curIdx, curCapacity) => {
        if (!curIdx) {
            return 0;
        }
        let weight = goods[curIdx].weight,
            value = goods[curIdx].value;
        if (weight > curCapacity) {
            return recurF(curIdx - 1, curCapacity);
        }
        let vPick = recurF(curIdx - 1, curCapacity - weight) + value,
            vNotPick = recurF(curIdx - 1, curCapacity);
        return Math.max(vPick, vNotPick);
    };
    return recurF(goods.length - 1, capacity);
})(goods, 20);
console.log(knapsackRecur); //26
复制代码

我们来看看01背包的动态规划解法

动态规划解法

跟书架问题一样，想办法将子问题的解记忆化。由于方程里有两个状态（变量），因此我们需要用二维数组存储问题的解。我们先来看看下面这一张表。在线01背包表

可以看到我们将F(i, c)转换成二维表，i为行（从i件物品中选），c为列(背包容量为c)，每个单元格的值为F(i, c)的解。 我们先随便看一个单元格。

红色框起来的单元格（第4行，第13列），意思是：F(3, 12)，从前三件物品中挑选一些物品，使得容量为12的背包价值最大，价值为15。下面我们试着解释这个值是怎么来的。（可以先是思考一下：选不选神器）

由状态转移方程可得：F(3, 12) = max(F(2, 12-5) + 8 , F(2, 12))（绿色部分和蓝色部分）所以F(3, 12) = max(F(2, 7) + 8 , F(2, 12)) = max(7+8, 7) = 15。 分析到这里大家应该明白了，现在我们看看自底向上迭代求解的代码实现。

let goods = [
    {value: 0, weight: 0}, //方便对应下标
    {value: 3, weight: 2},
    {value: 4, weight: 3},
    {value: 8, weight: 5},
    {value: 10, weight: 9},
    {value: 5, weight: 4}
];
const knapsackDP = ((goods, capacity) => {
    //初始化二维数组，保存子问题的最优解
    let record = [];
    for (let i = 0; i < goods.length; i++) {
        if (!record[i]) {
            record[i] = [];
        }
        let weight = goods[i].weight,
            value = goods[i].value;
        for (let c = 0; c <= capacity; c++) {
            if (!record[i][c]) {
                record[i][c] = 0;
            }
            if (i - 1 < 0) {
                continue;
            }
            //商品i的重量大于背包容量，无法把商品i放到背包里
            if (weight > c) {
                record[i][c] = record[i - 1][c];
            } else {
                let vPick = record[i - 1][c - weight] + value,  //选的情况
                    vNotPick = record[i - 1][c];    //不选的情况
                record[i][c] = Math.max(vPick, vNotPick);   //最优情况
            }
        }
    }
    return record[goods.length - 1][capacity];
})(goods, 20);
console.log(knapsackDP);
复制代码

总结

动态规划更像是一种思想，类似分治，把复杂问题分解成多个子问题，简单化问题。同时记忆化问题的解，争取每个问题只求解一次，达到优化效果。因此动态规划适用于含有重叠子问题的问题。

本文属个人理解，旨在互相学习，有说的不对的地方，师请纠正。转载请注明原帖