初次见到动态规划是在王道论坛划水的时候，见到时简直一脸懵逼。最近在刷Leetcode发现大量的题目建议采用动态规划的解法，遂将相关概念整理如下。
在看大家对动态规划的解读时，发现很有意思的现象，就是大家对动态规划的解读点并不一致。有的是理论型：从动态规划的本质出发，因对动态规划与其他算法的异同进行解释。有的是实战型，直接列出动态规划问题的处理模式。大部分解答甚至会将一部分算法技巧也列入动态规划之中，比如重复记忆等。个人认为这种现象的出现恰是由于动态规划本身定位就存在争论。以下的解释将从理论出发，逐步过渡到实战中的步骤或技巧。
动态规划适用的问题与定义
主要参考知乎中[王勐]的回答
动态规划是对某一类问题的解决算法思路，这类问题具有两个特点：
- 最优子结构 : 每个阶段的最优状态，由之前某阶段的一个或者几个状态得到
- 无后效性 :而不管这些状态是怎么得到的。
一开始看不懂上面在说什么，接着向下看即可。很多解答中还提到了重复子问题，并将其列入动态规划的定义之中，我个人认为那并不是核心特点。要清楚动态规划的定位，那么首先需要弄清楚一系列的相关概念，例如递推、贪心、递归、搜索等等。
问题导入
在处理很多问题时，其实我们可以引入时间步的概念，比如迷宫问题，可以假设一个时间步走一次。那么每个时间步我们称其为阶段，而一个阶段可以有多种状态，比如你在第 $n$ 步可以自由的选择向尚未走过的多个方向前进，导致你的状态产生多个。
比如说我想计算第100个非波那契数，每一个非波那契数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数；每计算一个新状态所需要的时间也是常数且状态是线性递增的，所以时间复杂度也是线性的。
上面这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行（a[i]=a[i-1]+a[i-2]），不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。
上面是其回答的原句，比我自己举得例子要更加直观。阶段就是随着问题的开展，在某个时刻可能会得到的不同状态的集合。非波那契数列中，每一步会计算得到一个新数字，所以每个阶段只有一个状态。而迷宫问题，你可以有多种选择，自然你的阶段状态数是多个。从头开始走了几步就是第几个阶段，走了n步所处的位置我们称为一个状态，而走了n步所有可能到达的位置的集合就是这个阶段的所有可能的状态。虽然说起来很绕口，但是很好理解。
相关算法的适用问题
有了阶段，针对不同问题，计算新状态的方式是不同的，就需要不同的算法，从而衍生出递推、贪心、动归等等。
假设：问题存在n个阶段，并且每个阶段存在多个状态，不同阶段的状态数不一定相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。
共识：要计算出最终阶段的状态数，必然其经历了之前每个阶段的部分状态。
分歧：不同的问题对之前阶段状态的需求不同，导致了不同的算法。
贪心算法适用问题
贪心算法的特点便是鼠目寸光，“下一步的最优只需要由当前最优得到”。
例如棋盘问题：从棋盘左上角到右下角最短需要几步。我们已经知道，某个阶段存在多个状态，你走了n步，可以到达的位置很多，但是有哪些位置可以让你在第n+1步中走得最远呢？？？答案很明显，即是在第n步中走得最远的位置。
这类问题特点，下一步最优是从当前最优得到的，解决此问题，只需寻出每一步的最优值即可，解决此类问题的算法为贪心，计算的方法为递推。
搜索算法适用问题
搜索算法的特点是考虑全局问题，下一步的选择需要考虑之前所有阶段的状态。
例如迷宫问题，计算从起点到终点的最短路线时，只保存当前阶段的状态是不够的，题目要求你最短，故需要知道之前走过的所有位置。即使你当前阶段的位置不变，之前路线的不同会影响你之后选择的路线。这时需要保存之前每个阶段经历的状态，根据这些信息才能计算出下一个状态。每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，所以解的复杂度就是指数的，因此时间复杂度也是指数的。刚刚提到的之前的路线会影响到下一步的选择，这个令人不开心的情况就叫做有后效性。
此类问题的解决方式，就是暴力解决，也就是最直观的搜索算法。
动态规划适用问题
有一类问题，看似需要所有状态，但其实不用。
例如最长上升子序列问题，
假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢？需要从头到尾依次枚举是否选择当前的数字，每选定一个数字就要去看看是不是满足“上升”的性质，这里第i个阶段就是去思考是否要选择第i个数，第i个阶段有两个状态，分别是选和不选。哈哈，依稀出现了刚刚迷宫找路的影子！咦慢着，每次当我决定要选择当前数字的时候，只需要和之前选定的一个数字比较就行了！这是和之前迷宫问题的本质不同！这就可以纵容我们不需要记录之前所有的状态啊！既然我们的选择已经不受之前状态的组合的影响了，那时间复杂度自然也不是指数的了啊！虽然我们不在乎某序列之前都是什么元素，但我们还是需要这个序列的长度的。所以我们只需要记录以某个元素结尾的LIS长度就好！因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的，然后就得到了DP方程。
小结：
每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到，这些状态也是上一阶段**”最优”**状态.
这个性质叫做最优子结构；
而不管之前这个状态是如何得到的
这个性质叫做无后效性。
通过这一部分：
- 应该理解了最优子结构、无后效性,但还是偏抽象，接下来的例子中会进一步进行解释。
- 各种算法适用的问题类型。
动态规划的本质
知乎徐凯强 Andy的回答
在这一部分，不再是单纯的理论上理解动态规划的概念，其涉及了动态规划的思考方式与本质的讨论。
本质是什么
动态规划的本质，是对问题*状态的定义*和*状态转移方程*的定义。
动态规划中递推式的求解方法不是动态规划的本质。
维基百科定义
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
动态规划是通过拆分问题，定义问题与状态之间的关系，进而是问题能够通过递推（或分治）的方式解决。
作者认为如何拆分问题，是动态规划的核心。拆分问题，靠状态的定义与状态转移方程的定义。
什么是状态的定义
对于状态的定义就是你对问题从可拆分的角度重新对其定义。
例如经典的最长上升子序列问题：
给定一个数列，长度为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的长度”，就叫做对状态的定义。之所以把
做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。
对问题的定义可以有多种，这只是其中一种。作者在回答中对此有其他定义，但没必要均罗列到上面。
什么是状态转移方程
状态与状态之间的关系，就叫做状态转移方程。
比如，对于LIS问题，我们的第一种定义：
设
设A为题中数列，状态转移方程为：
（根据状态定义导出边界情况）
用文字解释一下是：
以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。
这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。
可以看出，状态转移方程就是带有条件的递推式。
动态规划迷思
缓存、重叠子问题、记忆化
这些仅仅是在DP问题中求解递推式的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。
上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，**不是动态规划的核心。**
递归
递归是递推式求解的方法。
小结：
在这一部分我们对动态规划的本质有了一个直观的理解，也就是状态定义 + 状态转移方程。通过拆分为子问题的思想对状态进行定义，通过定义分析获得状态间的递推公式。这就是动态规划的本质。
动态规划的样例解读
知乎阮行止解答
DAG最短路径
问题：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。
状态定义：记$f(P)$ 为从S点到P点的最少费用。
要想到达T点，要么经过C要么经过D
状态转移方程:$f(T) = \min{ f(C)+20 , f(D)+10}$
- 无后效性：一旦获得$f(P)$ ，并不关心$f(P)$ 是如何得到的。
- 最优子结构：对于P，我们当然只关心到P的最小费用，即f(P)。如果我们从S走到T是
，那肯定S走到Q的最优路径是
。对一条最优的路径而言，从S走到沿途上所有的点（子问题）的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。
既然这两个性质都满足，那么本题可以DP。式子明显为：
其中R为有路通到P的所有的点， 为R到P的过路费。
小结：
原答案中作者还有其他方面的阐述，这里不表。这里展示了DP算法中状态定义以及状态转移方程的样子，可作为经典理解。
DP问题的技巧
知乎 Mingqi 解答
在这一部分，我们会讨论动态规划非本质的技巧，但却常常能够是代码质量得到提升。其认为动态规划的特点有三个：
再次提及维基定义
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
- 把原来的问题分解成了几个相似的子问题。（强调“相似子问题”）
- 所有的子问题都只需要解决一次。（强调“只解决一次”）
- 储存子问题的解。（强调“储存”）
理解存储的好处
以斐波那契数列(Fibonacci)的例子：
1 | 1， 1， 2， 3， 5， 8， 13 ，21 ... |
其状态转移方程为：
.svg)
我们通常是从上至下分解问题，再向上返回结果。n=6时的计算图为：
出现大量重复计算，无法体现其子问题只解决一次的特点。可以利用存储子问题的解的方式，解决上述问题，一般利用数组存储。其计算图为：
这个例子其实并不是动态规划的经典例子，其使用单纯的递推，也是一样的结果。但可以用来理解存储重复子问题的效果。
理解动态规划算法的优势
这里的优势是相对于暴力解决法。还是以最长上升子数列的长度（LIS）为例：
给定一个数列：
最长上升子数列为：
其长度为4.
暴力解决方式：穷举法
其时间复杂度为：
.svg)
动态规划解决：
状态转移方程：
（根据状态定义导出边界情况）
其计算图为：
可以看到这里的计算量相较于穷举法已经下降了很多。
同样的可以使用存储的方式减少计算量。
未使用存储：
使用存储：
小结：
在这一部分我们能够理解动态规划中存储的重要性，其是动态规划高效的核心。
动态规划本身是将原问题通过某种定义，演变成可拆分为子问题的形式，通过解决小问题从而以递推或分治的方式解决大问题。那么其本身的形式，必然存在大量的重复子问题，通过存储的方式，可以有效的降低时间复杂度，减少不必要的计算。
DP的实践
上面的几部分内容，均针对如何更好地理解动态规划，并没有涉及深入的实践环节。像这样的解答网上也有很多，例如知乎帅地的答案就偏向于实践。
我个人在接触之时，也看了很多实践的帖子，我个人的感受为：很多帖子只是花式的告诉你如何操作你就解决了动态规划问题，但是你个人还是不知道如何审题，无法确认此问题是否是动态规划问题。而且很多帖子不讲DP的本质，一开始就告诉你先整个数组，用于存储，这就很懵逼，对于我这样的小白肯定是不友好的，就像做数学题只注重套路没有看到此题的本质。
大家所说的也是大同小异，无非是：
- 定义状态 2.寻找状态转移方程 3.寻找边界 4.存储
光说不做假把式，实际问题更需要灵活的解决，好吧，我去刷题啦。
