一、定义

动态规划（英语：Dynamic Programming，简称DP）是运筹学的一个分支，是通过把原问题分解为相对简单的子问题的方式求解复杂问题的一种方法。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划[1] 。

这里Programming不是编程的意思，而是决策。但这种决策不是一下就出来的，而是一步步多阶段(multistage)积累出来的。换句话说，我们需要一个决策，但这个决策太大了，我们做不了，所以需要把它递归到我们可以简单做出决策的状态，然后从这些状态开始，慢慢的“动态地”演进到最终的决策。

把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

动态规划没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理。动态规划问题一直是大厂面试时最频繁出现的算法题，主要原因在于此类问题灵活度高，思维难度大，没有很明显的套路做法。没有放之四海皆准的计算动态规划解决方案的公式。

动态规划算法是国际大学生程序设计竞赛（ACM）用得最多的算法之一，深入学习动态规划很重要。

二、基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：

①通过具有记忆功能的迭代自顶而下求解;

②一般采用迭代法通过自底而上求解。

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为它可以用空间换取时间，特别是规模比较大时，大幅减少搜索与计算的时间。

三、动态规划分类

动态规划一般可分为四类：

线性动态规划

例如：拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等；

区域动态规划

例如：石子合并, 加分二叉树,统计单词个数,炮兵布阵等；

树形动态规划

例如：皇宫守卫,贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等；

背包动态规划

例如：01背包问题,完全背包问题,分组背包问题,装箱问题,挤牛奶等。

四、适用条件

能采用动态规划求解的问题，通常要具备3个性质：

(1) 问题中的状态必须满足最优化原理

最优化原理的定义：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优决策。简而言之，一个最优化策略的子策略总是最优的。

最优化原理用数学语言描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。

最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构是指原问题的最优解包含子问题的最优解。证明见附录1。

(2) 问题中的状态必须满足无后效性

所谓的无后效性是指，下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结。

(3) 子问题重叠性

子问题重叠性即子问题之间是不独立的，一个子问题在下一阶段决策中可能被屡次使用到。

动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

子问题重叠不是使用动态规划的必要条件，但是问题存在子问题重叠的特性更能够充分彰显动态规划的优势。若是没有这条性质，动态规划算法同其它算法相比就不具有优点。

五、动态规划解题思路1、解题步骤1) 划分阶段

按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段必定要是有序的或者是可排序的，不然问题就没法求解。

2) 确定状态和状态变量

将问题发展到各个阶段时所处于的各类客观状况用不一样的状态表示出来。

DP状态的确定主要有两大原则：

最优子结构无后效性

例如：图5-1求得一条从A到G的最短路径？

图5-1

可以用Dijkstra算法求得， Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。动态规划主要是解决多阶段决策问题，并且阶段间存在着相互影响。该例子有7个阶段，初始阶段状态为A, 第2阶段状态有两个{B1，B2}, 第三阶段状态有4个{C1,C2,C3,C4}，等等。一个阶段可以有多个状态。

3) 确定决策并写出状态转移方程

由于决策和状态转移有着自然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。因此若是确定了决策，状态转移方程也就可写出。

我们只需要用分类讨论的思想来枚举所有小状态向大状态转移的可能性即可推出DP转移方程。

4) 初始条件和边界状况

给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。即设置初始值，考虑边界状况。

2、动态规划决策过程示意图

图5-2

六、应用

动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 。

例子1 0-1背包问题

现有n件物品和一个容量为c的背包。第i件物品的重量是重量为w[i]，价值是v[i]。已知对于一件物品必须选择取（用1表示）或者不取（用0表示），且每件物品只能被取一次（这就是“0-1”的含义）。求放置哪些物品进背包，可使这些物品的重量总和不超过背包容量，且价值总和最大。

1> 穷举法有两种方法：第一种方法，计算从n件物品中，取任意数量的物品有多少种取法？

利用高中的排列组合知识，分类取：

取0个物品，有1种取法；

取1个物品，有n种取法；

取2个物品，有n*(n-1)/2种取法；

...

取n个物品，有1种取法；

总共的取法为：

共有2ⁿ种取法，然后分别计算2ⁿ种取法的物品的总重量和总价值，选出其中满足条件（物品的重量总和不超过背包容量，且价值总和最大）的一种取法。

第二种方法，将n个物品排成一行，对于一件物品必须选择取（用1表示）或者不取（用0表示），想象成n个0、1组成的序列，如

00010...010；

01100...100;

10001...110;

...

利用高中的排列组合知识, 这样的序列有2*2*2*2...*2 = 2^n种。

0-1背包问题中的“0-1”就是这个意思。

每一个序列代表一种取法，选出其中满足条件（物品的重量总和不超过背包容量，且价值总和最大）的一种取法。

显然，穷举法的运行时间是O(2ⁿ)，当n很大时真的是慢如蜗牛。

2、回溯法

用回溯法实现就是要在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。具体方法如下： 

①对每一个物品i，对该物品只有选与不选两种决策，有n个物品，可以形成一棵 深度为n的决策树； 

②遍历这棵树，以枚举所有情况，最后进行判断，若重量不超过背包容量，且总价值最大，该方案就是最优的。

假设你是一个小偷，背着一个可装下6磅东西的背包，你可以偷窃的商品如下：

图6-1

为了让偷窃的商品价值最高，你该选择哪些商品？

初始的状态是（6，0），表示背包容量为6磅，背包内物品总价值为0美元。接下来，我们要开始做选择了。每加一件物品，有两种选择，选或者不选。选择一个物品时，背包的容量会减少，里面的物品总价值会增加。背包问题变成了决策树，如图6-1所示。

图6-2

子树叶蓝色标记是按照回溯法枚举的选取物品的剩余容量和总价值，红色标记是能偷窃的商品的最高价值4200美元。

小结：

优化方法： 

剪枝一：当重量大于背包的容量时，没有必要对剩下的物品进行决策； 

剪枝二：将剩下的所有物品都选取，其总价值也没有目前所求得的总价值还大的话，就可以返回。

回溯法枚举所有的解空间，时间复杂度是O(2ⁿ)。

3、动态规划法

与回溯法同样的例子，假设你是一个小偷，背着一个可装下6磅东西的背包，你可以偷窃的商品如下：

图6-3

为了让偷窃的商品价值最高，你该选择哪些商品？

第1步，我们从一个网格开始，将背包问题网格化。网格的行对应的是商品，列对应的是不同容量(1~6磅)的背包。如图6-4所示。

图6-4

第2步，我们先来一步一步做。首先来看第1行，加入2磅的吉他。第1个单元格表示背包的的容量为1磅。吉他的重量是2磅，这意味着它不能装入背包！第1行的其它单元格的背包的容量≥2磅，可以装入吉他，总价值是1500美元。如图6-5所示。

图6-5

第3步，再加入4磅的电脑。在第2行中的各单元格的总价值的计算公式如下：

S(2,j)=max {v[2]+S(1,c[j]-w[2]),S(1,j)}

S(2, j)---表示第2行，第j列的单元格的总价值；

v[2] --- 表示第2行的商品(即电脑)的价值；

w[2] --- 表示第2行的商品(即电脑)的重量；

c[j] --- 表示第j列的小背包的容量，一般c[j]=j；(例如，第1列背包的容量是1磅， 第2列的背包的容量是2磅， 第3列的背包的容量是3磅，...， 第6列的背包的容量是6磅)

c[j]-w[2] --- 表示加入电脑后，第j列的背包的容量减去电脑重量后的剩余容量，刚好对应着以前的列号。

S(1, j) --- 表示第1行第j列的单元格的总价值。

对计算公式第一种理解方法：

加入当前商品（电脑）后，当前行中的各单元格的总价值等于①与②的最大值。

①　当前加入的商品（电脑）的价值 + 上一行中剩余背包容量（当前行的各单元格对应的背包容量减去当前加入的商品的重量）所在的列对应的单元格的总价值；

②　同一列(即同一背包的容量)的上一行单元格(即上一次计算)的已经加入的商品的总价值。

对计算公式第二种理解方法：

如图中红色标记部分， 第2行第6列的计算总价值 = max { 第1行第2列的单元格的总价值$1500 + 当前电脑的价值$2000, 第1行第6列的单元格的总价值$1500 }， 即两者取最大值。 为什么是第1行第2列呢？因为第6列的容量是6磅，减去加入的电脑的重量4磅，剩余的容量为2磅，对应的就是第2列。

图6-6

第4步，再加入5磅的音响。在第3行中的各单元格的总价值的计算公式如下：

S(3, j) = max {v[3]+S(2,c[j]-w[3]),S(2, j)}

S(3, j)---表示第3行，第j列的单元格的总价值；

v[3] --- 表示第3行的商品(即音响)的价值；

w[3] --- 表示第3行的商品(即音响)的重量；

c[j] --- 表示第j列的小背包的容量，一般c[j]=j；(例如，第1列背包的容量是1磅，第2列的背包的容量是2磅， 第3列的背包的容量是3磅，...，第6列的背包的容量是6磅）

c[j]-w[3] --- 表示加入音响后，第j列的背包的容量减去音响重量后的剩余容量，刚好对应着以前的列号。

S(2, j) --- 表示第2行第j列的单元格的总价值。

对计算公式第一种理解方法：

加入当前商品（音响）后，当前行中的各单元格的总价值等于①与②的最大值。

③　当前加入的商品（音响）的价值 + 上一行中剩余背包容量（当前行的各单元格对应的背包容量减去当前加入的商品的重量）所在的列对应的单元格的总价值；

④　同一列(即同一背包的容量)的上一行单元格(即上一次计算)的已经加入的商品的总价值。

对计算公式第二种理解方法：

如图中红色标记部分， 第3行第6列的计算总价值 = max { 第2行第1列的单元格的总价值0 + 当前音响的价值 $3000, 第2行第6列的单元格的总价值$3500 }， 即两者取最大值。 为什么是第2行第1列呢？因为第6列的容量是6磅，减去加入的音响的重量5磅，剩余的容量为1磅，对应的就是第1列。

图6-7

经过第4步加入手机、第5步加入MP3后，计算得到满的网格数据，红色标记的最后一行就是对应的各容量能够获取的商品的最大总价值。例如：1磅的容量能获取$1200, 2磅的容量能获取$1700, 3磅的容量能获取$2700, 4磅的容量能获取$3200, 5磅的容量能获取$3200, 6磅的容量能获取$4200。

图6-8

小结：

问题1：再新加一件商品，沿着往下走时，最大价值有可能降低吗？

答案：不可能。每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低。

问题2：行的排列顺序发生变化时结果将如何？答案会随之变化吗？

假设你按如下顺序填充各行：手机、音响、电脑、MP3、吉他。网格将会是什么样的？

答案：没有变化。也就是说，各行的排列顺序无关紧要。

问题3：可以逐列而不是逐行填充网格吗？

答案：就这个背包问题而言，这没有任何影响，但对于其他问题，可能有影响。

动态规划先解决子问题，再逐步解决大问题。 对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。

0-1背包问题用二维矩阵的网格解决，矩阵的行表示n个物品，列表示背包逐步增长的容量, 是从1增长到c，也就是从小背包容量增长到待求背包容量。

其状态转移函数：S(i, j) = max { v[i] + S(i-1, j- w[i]), S(i-1, j)} 1≤i≤n, 1≤j≤c

S(i, j)---表示第i行，第j列的单元格的总价值；

v[i] --- 表示第i行的物品的价值；

w[i] --- 表示第i行的物品的重量；

j --- 既表示列号，又表示第j列的小背包的容量;

j-w[i] --- 表示加入物品后，第j列的小背包的容量减去该物品重量后的剩余容量，刚好对应着以前的列号。

S(i-1, j) --- 表示第i-1行第j列的单元格的总价值。

0-1背包问题的空间复杂度与时间复杂度均为O(n*c)，其中n为物品数，c为背包容量。

例子2 查字典 - 最长公共子串与最长公共子序列[2]

已知：假设你管理着字典网站。用户在该网站输入单词时，你需要给出其定义。 但如果用户拼错了，你必须猜测他原本要输入的是什么单词。例如，Alex想查单词fish，但不小心输入了hish。

求：Alex输入了hish，那他原本要输入的是fish还是vista呢？

解答：

1> 最长公共子串

如何将这个问题划分为子问题呢？你可能需要比较子串：不是比较hish和fish，而是先比较his和fis。每个单元格都将包含这两个子串的最长公共子串的长度。这也给你提供了线索，让坐标轴很可能是这两个单词。

第1步 建立网格，单元格全部初始化为0。如图6-9所示。

图6-9

第2步，计算单元格的值，如果两个字母不相同，值为0；如果两个字母相同，值为左上角邻居的值加1。如图6-10所示。

图6-10

第3步，查找单词Fish和Hish的最长公共子串时，网格如图，最长公共子串为ish。如图6-11所示。

图6-11

查找单词hish和vista的最长公共子串时，网格如图，最长公共子串为is。如图6-12所示。

图6-12

所以，Alex输入了hish，那他原本要输入的是fish而不是vista。

伪代码实现如下：

if (word_a[i] == word_b[j])     //两个字母相同    cell[i][j] = cell[i-1][j-1] + 1;else                          //两个字母不相同    cell[i][j] = 0;

2> 最长公共子序列

假设Alex不小心输入了fosh，他原本想输入的是fish还是fort呢？

我们使用最长公共子串公式来比较它们。如图6-13所示。

图6-13

最长公共子串的长度相同，都包含两个字母！但fosh与fish更像。

图6-14

这里比较的是最长公共子串，但其实应比较最长公共子序列：两个单词中都有的序列包含的

字母数。如何计算最长公共子序列呢？

图6-15

最终的网格如下。

图6-16

伪代码实现如下。

if (word_a[i] == word_b[j])    cell[i][j] = cell[i-1][j-1] + 1;else    cell[i][j] = max(cell[i-1][j], cell[i][j-1]);

小结：生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。比较字符串的相似程度。编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！七、动态规划算法的局限性

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。

动态规划的维数就是指状态变量的维数，而不是指决策变量或策略的维数。状态变量的维数过大，在应用动态规划的方法求解时将大大增加电子计算机的内存量。解题所需要的内存量一般按指数速度增加的。

因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”

八、附录附录1 证明最优子结构中原问题的最优解包含子问题的最优解

以0-1背包问题为例证明。

0-1背包问题： 给定n中物品和一个背包，物品i的重量是wi,其价值为vi,背包的容量为C。如何选择装入背包的物品，使得装入背包中物品的总价值最大？

0-1背包问题等价于一个整数规划问题：

图8-1

图8-2

九、参考资料

[1] Bellman的自传书 <Eye of the Hurricane: An Autobiography>

[2]《算法图解》Aditya Bhargava著，袁国忠译