动态规划理论与案例
一、为什么要使用动态规划
在前面的文章中，我们介绍了贪心算法、回溯算法，它们和动态规划一样，通常都可以用来解决多阶段决策最优解的问题。但是在一些场景下，使用它们的话，并不能解决或者不能很好地解决这种多阶段决策最优解的问题。
我们来看一个例子，假设我们背包能装15公斤重的东西，现在地上总共三种重量的物品若干，分别是1公斤、5公斤和11公斤，那么如何才能使得背包装满15公斤，并且物品数量最少？
如果使用贪心算法的话，每一步都选择当下最优的，那么肯定会选择11+1+1+1+1，那么背包中总共会有5件物品。
如果使用回溯算法的话，就会对1、5、11这三个数字组合成15的排列组合进行穷举，会造成很多肯定不是最优解的垃圾解法，比如15个1公斤重的物品放进背包里面这种肯定不是最优解的解法。这样就会有很高的算法时间复杂度，空耗计算机资源。
正确的解法应该是5+5+5，这个解法才是这个问题的最优解，那么如何找到一个算法来得到这个最优解呢？这就是我们今天要讲的主题——动态规划（Dynamic Programming，DP）。
二、动态规划理论
2.1 动态规划是怎么寻找最优解的？
还是以上面的例子作说明，我们构造一个二维数组，列表示背包中可能会有多少重量的东西，行表示第n次放入物品。
当前我们物品个数没有限制，但是规格只有1、5、11三种，那么在第一次选择物品放入背包的时候，只可能有三种状态，即背包此时重量只可能是1、5、11（见如下表格）；
在第二次选择物品放入背包的时候，我们又可以有三种选择，所以应该有九种结果，其中四种超出背包重量限制，所以不符合要求，还有两种重复了，所以此时的合法状态就有四种（见如下表格）；
在第三次选择物品放入背包的时候，同理，可以有十二种结果，排除超出背包重量的，和重复的，合法的有5种；此时背包重量首次达到了上限15，所以我们得到了最优解，即+5+5+5这个解法（见如下表格）。
这就是一个动态规划解决问题的思路，把问题分解为多个阶段，每个阶段对应一个决策，我们需要记录每一个阶段的可达状态，当然需要去掉不合法的，合并重复的。然后通过当前这一步得到的状态集合来推导下一个状态集合，如此动态地往前推进，直至遇到最优解。
和回溯算法相比，我们并没有计算所有的情况，那将是指数级增长的时间复杂度；我们把超出背包重量的给排除了，把重复的合并了，把得到最优解后剩下的合法解求解过程给终结了，所以效率上比回溯算法高效很多。
| 1（放入第一个物品） | 2（放入第二个物品） | 3（放入第三个物品） | 4（放入第四个物品） | 5（放入第五个物品）...... | |
|---|---|---|---|---|---|
| 0 | |||||
| 1 | S(+1) | ||||
| 2 | S(+1+1) | ||||
| 3 | S(+1+1+1) | ||||
| 4 | |||||
| 5 | S(+5) | ||||
| 6 | S(+5+1)(+1+5) | ||||
| 7 | S(+5+1+1)(+1+5+1)(+1+1+5) | ||||
| 8 | |||||
| 9 | |||||
| 10 | S(+5+5) | ||||
| 11 | S(+11) | S(+5+5+1)(+5+1+5)(+1+5+5) | |||
| 12 | S(+11+1) | ||||
| 13 | S(+11+1+1) | ||||
| 14 | |||||
| 15 | S(+5+5+5) |
再来一个例子，假设有如下这样一个路径图，要求从左上角通过右移、下移这两个操作来到达右下角的目的地，每个格子中的数字表示需要花费的代价，那么怎么走才能使得代价最小？
动态规划问题
我们当然可以通过回溯来穷举所有解法，但我们要尝试使用动态规划。首先确定这的确是一个多阶段寻找最优解的问题，而且，划分的步骤应该如下所示。
动态规划分阶段示意图
同样的，我们构造一个二维数组，其中的数值表示达到这个位置所需要花费的最小代价，即到达这个位置的最优解。然后逐步往终点方向推进，等到了终点时，此时的显示的代价就是我们需要的最优解。
动态规划求得最优解
如上这种方法被称为状态表转移法。但是要最终写成代码，我们还需要根据上述方法写成状态转移方程，只要有了方程，这个问题就算解决大半了。
我们注意到每个位置上的值都是上面或者左边位置上的值加上本位置上的值的最小值，所以可以得出一个状态转移方程如下：
mind_dist[i][j]=cost[i][j]+min(min_dist[i][j-1],min_dist[i-1][j])
这就有点类似递归了，只不过这里递归得到的都是一个最优子问题的解。当然，在求解每个位置的min_dist值的时候，因为存在重复子问题，所以我们需要将每个子问题的解存下来，供后续需要时直接使用。
2.2 什么样的问题可以考虑使用动态规划来解决呢？
-
多阶段决策最优解问题模型
判断当前这个问题是否是分为多个阶段来决策，从而寻找出最优解的？
将不同重量的物品放到背包中，就是一个多阶段决策，寻找最优解的问题模型。
-
最优子结构
当前问题的最优解包含了子问题的最优解。即，我们可以通过子问题的最优解来推导出父问题的最优解。
假设我们最终得到了最优解f(15)，那么它的前一个步骤肯定是f(14)、f(10)、f(4)其中的一个，并且只能是它们三者中最优的那个才能最终推导出最优解f(15)，所以f(15)肯定包含了其子问题的最优解。
-
无后效性
在推导父问题解法的状态时候，我们只需要关心其直接子问题的状态值，而不用关心这个子问题的状态值是怎么来的，并且这些子问题状态值不会受到后续解决父问题的影响。
最优解f(15)的推导只关心它的直接子问题f(14)、f(10)、f(4)，这些子问题是怎么得出的，和f(15)没有关系，而且并不会因为选择哪一个子问题推导出来f(15)，这三个子问题的状态都不会因此而发生变化。基本上只要符合多阶段决策最有问题模型的问题，都能够满足这个特性。
-
重复子问题
存在重复的子问题；
这个很好理解，f(14)的子问题中我们需要求解f(9)，而f(10)的子问题中也存在f(9)，这个f(9)就是f(14)和f(10)这两个问题的重复子问题。
三、动态规划使用场景举例
3.1 0-1背包问题
这个问题上面已经有例子了，不再赘述。
3.2 DAG最短路径问题
这个例子在原先讲解贪心算法的时候有提到过。
求解有向带权图最短路径
使用贪心算法求得的解是S->A->E->T，总代价为1+4+4=9；
而实际最优解是S->B->D->T，总代价为6。
那么如何利用动态规划来求解呢？同样的，我们需要构造一个二维数组，行是需要执行的步骤，列是所有的节点。我们把从起点S开始每一步的合法状态都列举出来，到达每个节点的代价值则用重复子问题中的最小值来代表，这其实就是最优子问题，然后基于每一步动态地往目标推进，最终到达终点T，此时计算出来的最优解就是全局最优解。
| step1 | step2 | step3 | |
|---|---|---|---|
| S | |||
| A | 1(S,A) | ||
| B | 2(S,B) | ||
| C | 3(S,C) | ||
| D | 4(S,B,D) |
||
| E | 5(S,A,E)(S,C,E) | ||
| F | 6(S,A,F) |
||
| T | 6(S,B,D,T) |
3.3 拼写纠错问题
- 编辑距离，将一个字符串转化成为另一个字符串，需要的最少编辑次数。编辑距离越大，说明相似程度越小，两个相同的字符串其编辑距离为0。
- 莱文斯坦距离，只允许通过增加、删除、替换字符这三个编辑操作，是衡量两个字符串差异程度的指标。
- 最长公共子串，只允许通过增加、删除两个编辑操作，是衡量两个字符串相似程度的指标。
以上两种编辑距离的求解过程就可以使用动态规划来解决，可以抽象为把一个字符串变成另一个字符串，求解需要的最少编辑次数。
四、和其它算法的比较
贪心算法、回溯算法和动态规划这三种可以划分为一类，它们都是用来解决多阶段决策最优解问题的解法思路。
其中，回溯算法是一种万能的方法，它通过穷举多阶段的所有路径来找到最优解，缺点就是算法的时间复杂度非常高，只适合小数据量问题的求解，大数据量场景下还是不建议使用它。
贪心算法和动态规划则是两种不同的解决思路，贪心算法比较短视，每个步骤只是选择当下最优的决策，其它决策都抛弃，它是通过每一步的最优来达成最终的最优。贪心算法不是万能的，有些场景下使用它并不能得到最优解。
动态规划则是每个步骤都把合法的状态列出来，动态地向目标推进，这样就不会漏掉全局最优解。但并不是所有问题都可以使用动态规划的，需要满足如上的一个模型三个特征才行。
分治算法单独划分为一类，它不是用来解决多阶段决策最优解问题的，比较适合解决大规模数据求解的问题，它能通过分解问题，合并答案从而达到大数据量问题求解高效的目的。
