看完就懂系列—动态规划

前言

动态规划的主要思想

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

动态规划的三要素:

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

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

动态规划经典问题

书架放法问题

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

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

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

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

文字来描述问题未免过于啰嗦，为了更好地分析问题，我们先对原问题进行建模。

问题建模

我们需要对问题进行建模，用一个方程来普适化表达这一问题。建立方程就需要确定变量（状态），变量的确定可以看我们在问题的每个阶段中做决策时受到什么因素影响。题目中限制死了每次只能放1或2本，那么在书架上能放满书有多少种放法，只跟书架的容量有关系，因此书架的容量可作为方程中的变量。设F(x)的解为将容量为x的书架放满书的总放法数，则原问题的解为F(10)。

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

• 书架已经放满9本（最后一次放1本，可理解为书架只有9的容量）
• 书架已经放满8本（最后一次放2本，可理解为书架只有8的容量）

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

递归求解

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本书的总放法。

x0123...

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...）。还是按照分解问题的思想来，得到解题思路再说。同样地，文字描述未免太过于啰嗦，我们对问题进行建模。

问题建模

还是先确定方程的变量（状态）。思考一下会影响我们在各阶段做决策的因素有什么(一般问题中能直接找到)？

问题求规定背包承重下，所装物品的最大价值，显然第一个变量是背包的承重量，设为c(capacity)。

每个物品的价值和重量都不同，选了物品1很可能会影响到后面物品的选择，同时物品的选与不选会影响到背包的剩余承重量，跟变量c有着关联。因此宝库中提供的物品为另外一个变量，设为i。

现在就可以对问题建立方程了：设F(i, c)的解为，从i件物品中，挑选一些物品放入剩余容量为c（capacity）的背包中，使的背包物品价值最大。则原问题的解为F(5, 20)。思考一下，怎么将F(5, 20)分解呢？

选与不选神器

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

首先背包剩余容量必须大于物品5的重量，否则根本放不下，放不下相当于不用考虑物品5，原问题的解等同于从前4件物品中，挑选一些物品放入背包中（目前背包什么都没装），背包物品总价值最大。表示为：F(4, 20)。

选了物品5，问题的解为，选了物品5了，背包价值为物品5的价值，再从前4件物品中，挑选一些物品放入背包中（目前背包已装物品5），背包物品总价值最大。方程表示为F(4, 20 - 物品5重量) + 物品5价值 = F(4, 16) + 5。

不选物品5，等同于不考虑物品5，问题的解为，从前4件物品中，挑选一些物品放入背包中（目前背包什么都没装），背包物品总价值最大。表示为：F(4, 20)。

到底选还是不选，判断选和不选的情况中，哪种情况的背包总价值高，选价值高的情况。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); 复制代码

总结

动态规划更像是一种思想，类似分治，把复杂问题分解成多个子问题，简单化问题。同时记忆化问题的解，争取每个问题只求解一次，达到优化效果。因此动态规划适用于含有重叠子问题的问题。解决动态规划问题的关键在于推导出状态转移方程。状态转移方程的推导过程可以参考如下：

• 在多阶段决策问题中，找到影响决策的因素（定义状态）。
• 根据状态对问题进行建模（用以状态为变量的方程来表示问题）。
• 将原问题分解成子问题（确定状态转移方程）。

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

转载于:https://juejin.im/post/5cf3b2236fb9a07f0052c455

总结

以上是生活随笔为你收集整理的看完就懂系列—动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。