什么是动态规划（Dynamic Programming）？动态规划的意义是什么？

动态规划中递推式的求解方法不是动态规划的本质。

我曾经作为省队成员参加过NOI，保送之后也给学校参加NOIP的同学多次讲过动态规划，我试着讲一下我理解的动态规划，争取深入浅出。希望你看了我的答案，能够喜欢上动态规划。

0. 动态规划的本质，是对问题状态的定义和状态转移方程的定义。

引自维基百科

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。

而拆分问题，靠的就是状态的定义和状态转移方程的定义。

1. 什么是状态的定义？

首先想说大家千万不要被下面的数学式吓到，这里只涉及到了函数相关的知识。

我们先来看一个动态规划的教学必备题：

给定一个数列，长度为N，
求这个数列的最长上升（递增）子数列（LIS）的长度.
以
1 7 2 8 3 4
为例。
这个数列的最长递增子数列是 1 2 3 4，长度为4；
次长的长度为3， 包括 1 7 8; 1 2 3 等.

要解决这个问题，我们首先要定义这个问题和这个问题的子问题。

有人可能会问了，题目都已经在这了，我们还需定义这个问题吗？需要，原因就是这个问题在字面上看，找不出子问题，而没有子问题，这个题目就没办法解决。

所以我们来重新定义这个问题：

给定一个数列，长度为N，
设为：以数列中第k项结尾的最长递增子序列的长度.
求 中的最大值.

显然，这个新问题与原问题等价。

而对于来讲，都是的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第中某项结尾的LIS。

上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。

之所以把做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。

对状态的定义只有一种吗？当然不是。

我们甚至可以二维的，以完全不同的视角定义这个问题：

给定一个数列，长度为N，
设为：
在前i项中的，长度为k的最长递增子序列中，最后一位的最小值. .
若在前i项中，不存在长度为k的最长递增子序列，则为正无穷.
求最大的x，使得不为正无穷。

这个新定义与原问题的等价性也不难证明，请读者体会一下。

上述的就是状态，定义中的“为：在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。

2. 什么是状态转移方程？

上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。

比如，对于LIS问题，我们的第一种定义：

设为：以数列中第k项结尾的最长递增子序列的长度.

设A为题中数列，状态转移方程为：

（根据状态定义导出边界情况）

用文字解释一下是：

以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。

第二种定义：

设为：在数列前i项中，长度为k的递增子序列中，最后一位的最小值

设A为题中数列，状态转移方程为：

若则
否则：

（边界情况需要分类讨论较多，在此不列出，需要根据状态定义导出边界情况。）

大家套着定义读一下公式就可以了，应该不难理解，就是有点绕。

这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。

可以看出，状态转移方程就是带有条件的递推式。

3. 动态规划迷思

本题下其他用户的回答跟动态规划都有或多或少的联系，我也讲一下与本答案的联系。

a. “缓存”，“重叠子问题”，“记忆化”：

这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。

上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。

b. “递归”：

递归是递推式求解的方法，连技巧都算不上。

c. "无后效性"，“最优子结构”：

上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。

在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。对状态和“最优子结构”的关系的进一步解释，什么是动态规划？动态规划的意义是什么？ - 王勐的回答 写的很好，大家可以去读一下。

需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区：

动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。

有位答主说：

分治在求解每个子问题的时候，都要进行一遍计算
动态规划则存储了子问题的结果，查表时间为常数

这就像说多加辣椒的菜就叫川菜，多加酱油的菜就叫鲁菜一样，是存在误解的。

文艺的说，动态规划是寻找一种对问题的观察角度，让问题能够以递推（或者说分治）的方式去解决。寻找看问题的角度，才是动态规划中最耀眼的宝石！（大雾）

希望本文不仅能告诉你什么是动态规划，也能给你一种如何分析、求解动态规划问题的思考方式。

0001b 动态规划介绍

1. 运筹学中的动态规划

动态规划(Dynamic Programming，简称DP)是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。把多阶段问题变换为一系列相互联系的的单阶段问题，然后逐个加以解决。

这里提到动态规划其实是一种数学方法，是求解某类问题的一种方法，而不是一种特殊的算法，没有一个标准的数学表达式或明确定义的一种规则。

比如我们接触过的”排序算法“，”二叉树遍历算法“等，这些算法都是有固定范式的，遇到此类问题我们只需要照搬算法即可。但动态规划却不是，它告诉你的是解决某类问题的一种思路，或者是一种更高意义上的算法，是一种道，而不是术。所以动态规划难就难在我们即使学会了这种思想，遇到具体问题也需要具体分析，很可能因为我们构造不出动态规划所需要的形式而无法解决，甚至根本想不到这是一个动态规划问题。

如下图。我们在解决某些最优问题时，可将解决问题的过程按照一定次序分为若干个互相联系的阶段（1, 2, ..., N），从而将一个大问题化成一系列子问题，然后逐个求解。

在每一个阶段都需要作出决策，从而使整个过程达到最优。各个阶段决策的选取仅依赖当前状态（这里的当前状态指的是当前阶段的输入状态），从而确定输出状态。当各个阶段决策确定后，就组成了一个决策序列，这个决策序列就决定了问题的最终解决方案。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程。

前面说到”仅需要依赖当前状态“，指的是问题的历史状态不影响未来的发展，只能通过当前的状态去影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性(即马尔科夫性)。 上图中，在阶段2时所做出的决策，仅依赖于阶段2的输入状态，与阶段1的输入状态无关。

动态规划定义中提到按照一定次序分成互相联系的子阶段，这里面的关键是互相联系。如果是独立的子问题，那是分治法，分而治之的意思。动态规划将一个大问题化成一族互相联系、同类型的子问题。既然是同类型，我们在逐个解决子问题的时候，就可以利用相同的决策，从而更容易的解决问题。互相联系利用前面已经解决的子问题的最优化结果来依次进行计算接下来的子问题，当最后一个子问题得到最优解时，就是整个问题的最优解。

这里面包括两个关键点：

1. 每一个阶段可能包括很多状态，前后阶段的状态通过决策联系在一起。如果要利用前阶段子问题的结果解决现阶段的子问题，必须要能够建立前后阶段状态的转移关系，最好可以通过方程表示。用专业术语我们又叫做”状态转移方程“。
2. 我们在衡量最优解的时候需要有一个指标函数，最优解就是让这个指标函数达到最优值，比如最大或者最小。如果我们可以将问题拆分成子问题，那么这个指标函数也必须具有分离性，也就是必须能够利用子问题的最优递推的求出整体最优。当整体最优求解出以后，就可以知道各个子问题的最优解。

可以看到，上面两个关键点无论是状态转移方程还是指标函数分离，其实都是需要列出递推关系式，如果恰当的选取状态，让每个子问题的状态能够表示出子问题的最优解，那我们就可以用状态转移方程递推求出指标函数的最优解。实际中我们也是经常这么做的。

2. 动态规划举例

上面的描述如果觉得有些抽象，可以看完下面的栗子再回过头看一遍，可能理解会更加深刻。如下图，要求出从A点到F点的最短路径。我们来分析一下如何用动态规划的思想来解决这个问题。

第一步，我们将这个问题拆分成多阶段子问题，然后选择状态变量，使其满足无后效性。如下图，我们分为3个阶段。阶段1有1个输入状态A，输出状态B, C，阶段1的输出状态就是阶段2的输入状态，所以阶段2有2个输入状态{B, C}，阶段3有2个输入状态{D, E}，输出状态F。

以状态D为例，从状态D做决策选择最短路径的时候，我们只关心如何从D到F，不关心从前一阶段是从B还是C到达的D，满足无后效性。

第二步，确定决策集合。假设当前处在状态B，此时的允许决策集合就是 { D, E}，不同的决策会使得状态转移的路径不同，从而影响到下一个状态。当选择决策D时，对应的决策变量 。

第三步，确定状态转移方程、分离指标函数。

把从A到F的路径看成一个指标函数，这个指标函数的最小值就是最短路径。我们接着分离指标函数，找到递推关系。

我们用 表示从初始节点到第k阶段节点s的最短路径，当我们这样拆成子问题时，它既是整个问题的最优子结构（因为当k为N时，就是原问题本身），又可以定义成状态。 如果我们可以列出状态转移方程，也就可以递推求出最优解。

,

接下来就是如何利用最短路径推导出 ，从而构造出递推方程。我们有

同理有

有了上面这个状态转移方程，我们可以容易的求出

于是，上述问题的最短路径就是7。

3. 《算法导论》中的动态规划

动态规划的思想最初是由美国数学家贝尔曼在1951提出，前面我们也是从数学的角度去理解动态规划，它背后的思想是最优化定理。

在《算法导论》中也讲到了”动态规划“，我在前面提到，动态规划难就难在它不是一成不变的，是一种更高意义上的算法思想；它不是一种特殊的招式，而是无招胜有招，需要见招拆招。

从算法的角度来看，什么时候可以使用动态规范方法解决问题呢？这其中包括了两个要素，分别是”重叠子结构“和”最优子结构“。下面我们就借鉴《算法导论》，从算法的维度再来剖析一遍动态规划，看看和运筹学中的”动态规划“能不能找到什么共性？

1）重叠子结构

前面我们说动态规划是将一个多阶段问题分成几个相互联系的单阶段问题。而这几个相互联系的单阶段问题一定要是一族同类型的子问题，这样分成多阶段决策才是有意义的，否则我们每次面对的决策都是不同的问题，也就失去了分成单阶段的意义。

在算法上，我们把这种同类型的子问题又叫做”重叠子结构“。重叠不是相同，而是同类型，我们必须得利用前面子结构计算出的结果，用递推不断地调用同一个问题。

所以说，《算法导论》中的重叠子结构其实就是对应了数学中将多阶段问题分成单阶段问题的过程，只不过强调了这个单阶段问题必须是”重叠的“，这样才能够用同一种算法递推地解决问题。

2）最优子结构

利用前面已经解决的子问题最优解来构造并解决后面的子问题。能够构造的前提就是要满足指标函数的分离性，也就是全局最优解一定能够拆成子问题的最优解，从而递推解决。

对应到算法中，就是按照自底向上的策略，首先找到子问题的最优解，解决子问题，然后逐步向上找到问题的一个最优解。也就是说，整体问题的最优解包括了子问题的最优解。我们又叫做”最优子结构“。

这么分析来，《算法导论》中的最优子结构其实就是对应了数学中指标函数的分离性。两者只是从不同的维度描述而已。

所以动态规划在数学上和算法上的描述归根到底都是相同的，只是使用数学语言和算法语言的区别。

于是我们按照定义看看如何辨别DP问题。

先来看看必须提到的斐波那契数列，它的递推表达式为

• 从数学上来看，这个问题本身不是一个最优化问题，也就是没有一个指标函数去衡量最优值；而且需要依赖当前状态和前一个状态，不满足无后效性。所以从数学上来说它不是一个动态规划问题。
• 从算法上看，它虽然具有重叠子结构，但本身不是一个最优化问题，没有最优子结构，不是动态规划问题。虽然不满足无后效性，但是依赖有限个状态，同样可以列出状态转移方程。

虽然不是DP问题，但我们也没有必要那么教条，毕竟动态规划是用来一系列比较复杂的最优化问题，当然也可以利用动态规划当中的一些思想去解决类似的问题，因为相对于动态规划问题，斐波那契数列这种问题算是太小儿科了。

接下来我们看看什么样的问题是动态规划问题，以及如何运用上面介绍的步骤进行解题。

0010b 刷题

学了这么多动态规划的知识，需要刷刷题，由简入难，体会一下动态规划到底怎么用，如何将这种思想付诸于实践。如果觉得学的比较明白了，也需要刷刷题打击一下自信。（下面所有的解法都是为了详细提现如何使用动态规划，所以在时间复杂度和空间复杂度上都没有经过优化）

题目来自LeetCode

53. 最大子序和 (难度：简单)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

虽然难度为简单，但我觉得从动态规划的角度来考虑，这道题一点也不简单。

首先找关键字，要求最大子序和，有关键字”最大“，是一道最优问题，可能是一道DP问题。

接下来就是最关键的一步，也是最难的一步。如何构造出子问题，每个子问题必须满足”重叠子结构“和”最优子结构“两个要求才能用动态规划来解决。

首先想到的是如果原问题是”N个元素的最大子序和“，那子问题能不能是”N-1个元素的最大子序和“，也就是能否找到N-1个元素最大子序和跟N个元素最大子序和的递推关系，并且能用同类型的算法去解决。如何可以找到，就满足”重叠子结构“和”最优子结构“。

首先来看其中的一种情况。

如果我们求出了 ，其中 表示从第1个元素到第N个元素的最大子序和，如下图。那么的解对的解有没有帮助呢？也就是能不能求出 和 的递推关系呢？

容易得出 ，最大子序列是第2个元素1。而 ，最大子序列是第4个元素4。求最大子序和必须找到最大子序列，当我们求 时，由于 中最大子序列的位置是不知道的，所以新增加一个元素时，这个元素是否能添加到前面的最大子序列中也是不知道的。比如对于子序列{ 2, -2}，最大子序和为2，新添加一个元素后子序列变为{2, -2, 1}，此时虽然添加了一个正的元素1，但无法利用前一个最大子序列，因为无法判断是否应该连在一起构成一组新的最大子序列。

所以这里问题就来了，这种子问题的构造方式无法构成”最优子结构“，也就是子问题的最优解无法递推地解决下一个子问题，无法列出状态转移方程，也就不能用动态规划来解决。所以说即使理解动态规划，但是子问题的构造方式还是十分有技巧的，否则动态规划的大招还是使不出来。我们要换另外一种构造子问题的方式。

前面构造的子问题是”前N个元素的最大子序和“，产生了一个问题，在增加一个新元素的时候，不知道前一个最大子序列的位置，所以无法判断新添加的元素是否应该加到前面的子序列中，因为有可能被中间不在子序列中的元素打断，所以也就无法构造最优解。

那如果想要新添加的元素不被中间的元素打断，就得在构造子序列 的时候保证每一个子序列都是以第n个元素结尾。于是子问题变为"前N个元素中以第N个元素结尾的最大子序和"。

如上图，第n个元素为-3，子序列中必须包含这个元素，所以

这样，新添加一个元素4构成 的时候，我们只需要判断 是否为正即可。如果是正数，对子序列和起到正增益的作用，则包含到新的子序列中；否则，抛弃前面的子序列。例如

于是，我们可以构造出 的递推关系

胜利就在前方，但是这样构造有一个问题，要求的是最大子序和，而不是以某个元素结尾的最大子序和。但是无论是最大子序列是什么，一定是以1 - N当中的某一个元素结尾，所以前面拆分的子问题是最优子问题，我们只需要找到最优子问题当中解的最大值，就是最终问题的解。下面上代码

       public class MaxSubArray {     public static int maxSubArray(int[] nums) {         // 构造子问题，dp[n]代表以n结尾的最大子序和         int[] dp = new int[nums.length];         // 状态初始化         dp[0] = nums[0];         int ans = nums[0];         for (int i = 1; i < dp.length; i++) {             // 分离指标函数，列出状态转移方程             dp[i] = Math.max(dp[i - 1], 0) + nums[i];              // 最优解是最优子结构当中的最大值             ans = Math.max( ans, dp[i] );         }         return ans;     }      public static void main(String[] args) {         int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};         System.out.println("MaxSubArray Length = " + maxSubArray(nums));     } }     

输出结果

       MaxSubArray Length = 6     

通过这个问题可以看到，动态规划最难的部分是构造状态，使其满足最优子结构，并且列出状态转移方程。如果这部分完成了，那代码其实就是将我们的思路写下来而已。

72. 编辑距离 (难度：困难)

据说这道题也是鹅厂的面试题，在测量两段基因相似度的时候会采用编辑距离这一概念，编辑距离越短，则基因越相似。

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作：
1. 插入一个字符
2.删除一个字符
3.替换一个字符
示例: 输入: word1 = "horse", word2 = "ros" 输出:3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

同样，看到了关键字”最少“，应该是一道DP问题。

首先，构造子问题1 word1="h"，word2=”r"时的最小操作数 ,其中下标1,1表示word1和word2的字符串长度都是1。但是即使知道这个最少操作数，如何构造下一个子问题呢？下个子问题貌似还不明确，也就是没有找到状态转移方程，那么其实状态还是没有被明确定义出来。下一个子问题应该如何定义字符串呢？我试着将问题最简化，子问题2只在word1增加一个字符，变为 word1="ho"，word2="r"的最少操作数 。显然，子问题2的最少操作数就是在子问题1基础上将字符'o'删除，也就是 。那如果有一个子问题2’是word1="h"，word2="ro"，同样，就是在子问题1基础上增加一个字符'o'，也就是 。我可能会想到列出这样一个等式

但很快，我就会发现这个等式有一个问题，如果要求 ，是应该用 还是用 呢？由于要最少操作数，我可能会把上面的式子改成

好像已经找到状态转移方程了。不会这么简单吧，我们回头看一看题目，状态转移方程中仅用到了插入，删除两个操作，还少了一个替换字符的操作，也就是如果已经得出来 ，我只需要将两个字符串中位于m+1和n+1的字符串进行替换，同样也可以实现转换。于是我再修正一下上式，使其包含替换的操作

细心的朋友可能会想到，替换的操作不一定是必须的。比如题目中给的例子，如果解决了word1=”h"，word2=”r“这个子问题1解决了以后，那么对于word1="ho", word2="ro"这个子问题也就解决了，因为最后一个字符是相同的，无需任何操作。所以上面的方程还需要改造。

状态转移方程我们已经列出来了，我们用表格来展现一下上面的关系。

但是递归需要初始条件，那怎么进行初始化呢？从上面的表格来看，也就是如何初始化表格的最左侧一列和最上面一行。

到此，有了初始化条件和状态转移方程，我们就可以写具体实现了。这样初始化虽然可以实现，但有一个不太好的地方，就是初始化是需要依赖输入字符串，如果出现相同字符，初始化值是不同的。而我们希望的是一套统一的算法，无论输入字符串是什么，初始化方式是固定的。那么我们应该如何改造初始化，让它不依赖于输入字符串呢？那就是初始子问题尽量的简单。上面的初始化对应的是 和 ，我们能不能再简化初始化条件？让 和 由更基本的初始化条件推导出来呢？所以我们需要定义 和 ，那 对应的就是空字符，如下图。

有了空字符，则初始化条件就简单了，由空字符生成任意字符串，都是加字符，所以第一行和第一列对应的就是字符个数，这样初始化条件就简单了。而其它的位置，我们只需要按照前面的递推关系填进去就可以了，如下图，有点像填杨辉三角形。

其中绿色的部分是因为字符相同，直接取左上方的值，其它则是取左，上，左上方的最小值加1。表格填完了，下面按照前面的思路上代码，

       public class MinDistance {     public static int minDistance(String a, String b) {         int length1 = a.length();         int length2 = b.length();         int[][] dp = new int[length1 + 1][length2 + 1];                  // 初始化第一列         for (int row = 0; row < length1 + 1; row++) {             dp[row][0] = row;         }         // 初始化第一行         for (int column = 0; column < length2 + 1; column++) {             dp[0][column] = column;         }          for (int row = 1; row < length1 + 1; row++) {             for (int column = 1; column < length2 + 1; column++) {                 // 如果字符相等，则直接取左上方的值                 if ( a.charAt(row - 1) == b.charAt(column - 1) ) {                     dp[row][column] = dp[row-1][column-1];                 } else { // 否则取左，上，左上三个值中的最小值+1                     dp[row][column] = Math.min(                         dp[row-1][column-1],                          Math.min(                             dp[row][column-1],                              dp[row-1][column]                          )) + 1;                 }             }         }         // 递推后，表格最右下方的值就是整个问题的最优解         return dp[length1][length2];     }      public static void main(String[] args) {         String a = "horse";         String b = "ros";         System.out.println("minDistance Result: " + minDistance(a, b));     }  }     

输出结果

       minDistance Result: 3     

887. 鸡蛋掉落 （难度：困难）

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。 你的目标是确切地知道 F 的值是多少。 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？ 示例 1： 输入：K = 1, N = 2 输出：2
解释： 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。 如果它没碎，那么我们肯定知道 F = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

这道题也很经典，作为思考题吧。

0011b 总结

解释了两道题，相信已经对动态规划有一定感觉了，难点不是动态规划本身，而是如何准确的定义状态，列出状态转移方程。从我的经验来看，可以按以下两个方法尝试

1. 将问题简化成最简，定义状态，这样更有利于观察到问题本质，寻找递推关系。
2. ”大胆假设，小心求证“。在定义状态的时候，如果无法找到状态转移方程，可以大胆尝试几种不同的状态定义方式，不要怕错，然后再仔细考察是否满足最优子结构，列出状态转移方程。