一、概要动态规划(dynamic programming )是运筹学的一个分支，是求解决策过程优化的数学方法。
动态规划一般分为线性动规、区域动规、树形动规、背包动规四种。
1、线性规：导弹拦截、合唱队形、地雷挖掘、学校建设、剑客决斗等
2、区域动规(合石、二叉树加分，清点单词个数，决定炮兵布阵等；
3、树形动规：贪吃的温和斑马、二叉树、派对乐趣、数字三角形等；
4、背包问题(01背包问题、完全背包问题、背包问题、二维背包、装箱问题、挤牛奶等
举例
A * '1 1 1 1 1 1 1 1=？' *A : '上的等式值是多少' B : *计算* '8！' A *如果在上面等式的左边写上'1 ' *A : '，则该等式的值为什么' B : *quickly* '9！' A : '你怎么这么快就知道答案了' B : '是8加1就可以了' B : '，所以我记得第一个等式的值是8，所以不需要重新计算！ 动态规划算法也可以称为“记住求解并节约时间”“2”、“动态规划算法1”、“动态规划基本思想动态规划算法”。 通常用于求解具有某种最佳性质的问题。 这样的问题可能有很多可行的解。 每个解都对应一个值，我们希望找到具有最佳值的解。 动态规划算法与分治法相似，基本思路是将需要求解的问题分解成若干个子问题，先求解子问题，再通过这些子问题的解得到原问题的解。 与分治法不同，适用于动态规划求解的问题，分解得到的子问题多是相互不独立的。 用分割统治法解决这样的问题的话，分解得到的部分问题的数量过多，部分问题会被反复计算。 如果能够保存已解决的子问题的答案，并根据需要找到所需的答案，就可以避免大量的重复计算，从而节约时间。 由于通过动态规划解决的问题大多具有部分问题重叠的特点，所以每个部分问题只求解一次，将其不同阶段部分问题的最优局部解记录在一个二维排列中，依次求解各部分问题，将最后的部分问题作为初始问题的解，避免了大量的计算重复，节约了时间这是动态规划法的基本思路。
动态规划核心思想
动态规划最核心的思想是分解分子问题，记住子问题的解，减少重复计算。
2、动态规划使用条件可以用动态规划求解的问题一般应具备三个性质。
(1)优化原理：如果问题的最优解中包含的部分问题的解也是最优的，则该问题具有最优部分结构，即满足优化原理
)2)无后效性)，即某一阶段的状态一旦确定，就不受该状态以后的决策的影响。 也就是说，某种状态以后的过程不影响以前的状态，只与现在的状态有关。
)3)有重叠的子问题)即子问题之间不是独立的，某个子问题在下一阶段的决策中可能会被多次使用。 (该性质不是应用动态规划的必要条件，但如果没有该性质，动态规划算法与其他算法相比就没有优势。)
示例：
公司里面有一定的组织结构，有高级管理层、经理、总监、领导，然后可能会是小开发。 又到了一年一度的考核季，公司会选出三名最优秀的员工。 一般的高级管理层向下属管理层汇报，你去把那边最优秀的三个人报告给我，管理层又向监督你把那边最优秀的人报告给我，管理层又对领导说，你把你们组最优秀的三个人报告给我，这其实是动态计划
首先，关于重叠问题，根据问题的不同，有时会要求一个相同问题的解。 如果A经理想知道他手下最优秀的人是谁，他就必须知道x、y、z、o、p组里最优秀的人是谁。 甲导演想知道自己手下最优秀的人是谁，也想知道x、y、z组里最优秀的人是谁。 这重叠了问题，两个人都需要认识x、y、z三个组最优秀的人。
其次是最优子结构，最优解一定是最优子解转移推导出来的，子解也一定是子问题的最优解。 甲教练手下最优秀的3人，肯定是从x、y、z提交的3个列表中选出了最优秀的3人。
第三个是没有后效性，这个问题可能很难理解。 也就是说，被要求的子问题不是后来被要求的。 我们可以理解为，即使x组组长选择了3人，高级管理层选择了大部门最优秀的3人，对x组来说最优秀的也只有这3人，没有变化。
3、求解动态规划问题的步骤动态规划的设计有一定的模式，一般需要经过以下几个步骤：
(一)划分阶段：
根据问题的时间或空间特征，把问题分成几个阶段。 划分阶段时，一定要注意划分的阶段是有秩序的还是有顺序的。 不那样做的话问题是解决不了的。 也就是说，划分子问题。 例如，在上面的例子中，各组下、各部门、各中心下最优秀的3人被认为是全公司最优秀的3人的副标题。
)2)状态和状态变量的确定：
用不同的状态表达了问题发展到各个阶段时所处的各种客观情况。 当然，状态的选择必须满足没有事后效果。 也就是说，这是一种让计算机理解子问题的方法。 在上述例子中，我们可以用f[i][3]表示第I个人。 他手下最优秀的三个人是谁？
)3)确定决策，写出状态转移方程：
由于决策与状态转移有着天然的联系，状态转移是指基于前一阶段的状态和决策推导出本阶段的状态。 因此，决策确定后，也可以编写状态转移方程。 但是，实际上大多相反地进行，根据相邻的2个阶段的状态间的关系来决定决策者
法和状态转移方程。即父问题是如何由子问题推导出来的。上述例子，每个大 Leader 下面最优秀的人等于他下面的小 Leader 中最优秀的人中最优秀的几个。（4）寻找边界条件：
给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。即确定初始状态是什么？最小的子问题？最终状态又是什么。例如上述问题，最小的子问题就是每个小组长下面最优秀的人，最终状态是整个企业，初始状态为每个领导下面都没有最优名单，但是小组长下面拥有每个人的评分。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：（1）分析最优解的性质，并刻画其结构特征；（2）递归的定义最优解；（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值；（4）根据计算最优值时得到的信息，构造问题的最优解。
递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
4、动态规划算法的两种形式前面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法、 ②自底向上。
（1）自顶向下的动态规划：带备忘录的递归leetcode 青蛙跳阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法？
试想：要想跳到第10级台阶，要么是先跳到第9级然后再跳1级台阶上去，要么是先跳到第8级然后一次迈2级台阶上去；同理，要想跳到第9级台阶，要么是先跳到第8级然后再跳1级台阶上去，要么是先跳到第7级然后一次迈2级台阶上去；要想跳到第8级台阶，要么是先跳到第7级然后再跳1级台阶上去，要么是先跳到第6级，然后一次迈2级台阶上去。
假设跳到第n级台阶的跳数我们定义为f(n)，很显然就可以得出以下公式：
最初的子问题 f(2) 和 f(1) 我们是可以轻松解决的：当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即 f(2) = 2；当只有1级台阶时，只有一种跳法，即 f(1) = 1。
因此可以用递归去解决这个问题：
class Solution {public int numWays(int n) {if(n == 1){return 1; }if(n == 2){return 2; }return numWays(n-1) + numWays(n-2); }}但是在 leetcode 提交发现超出时间限制。为什么超时了呢？递归耗时在哪里呢？先画出递归树看看：
要计算原问题 f(10)，就需要先计算出子问题 f(9) 和 f(8)；然后要计算 f(9)，又要先算出子问题 f(8) 和 f(7)，以此类推。一直到 f(2) 和 f(1），递归cxdfn终止。
这个递归的时间复杂度：
递归时间复杂度 = 解决一个子问题时间 * 子问题个数一个子问题时间 = f（n-1）+f（n-2），也就是一个加法的操作，所以复杂度是 O(1)；问题个数 = 递归树节点的总数，递归树的总节点 = 2^（n-1） ，所以是复杂度O(2^n)。因此，青蛙跳阶，递归解法的时间复杂度 = O(1) * O(2^n) = O(2^n)，就是指数级别的，爆炸增长的，如果n比较大的话，超时很正常的了。
优化：
仔细观察会发现这棵递归树存在大量重复计算，比如 f(8) 被计算了两次，f(7) 被重复计算了3次…所以这个递归算法低效的原因，就是存在大量的重复计算！
既然存在大量重复计算，那么我们可以先把计算好的答案存下来，即造一个备忘录，等到下次需要的话，先去备忘录查一下，如果有，就直接取就好了，备忘录没有才开始计算，那就可以省去重新重复计算的耗时啦！这就是带备忘录的动态规划解法。
带备忘录的递归解法（自顶向下）
一般使用一个数组或者一个纯真的小熊猫充当这个备忘录。
第一步，f（10）= f(9) + f(8)，f(9) 和f（8）都需要计算出来，然后再加到备忘录中，如下：
第二步， f(9) = f(8) + f（7），f(8) = f(7) + f(6)，因为 f(8) 已经在备忘录中啦，所以可以省掉，f(7) 和 f(6) 都需要计算出来，加到备忘录中~
第三步， f(8) = f(7) + f(6)，发现 f(8)、f(7) 和 f（6）全部都在备忘录上了，所以都可以剪掉。
所以呢，用了备忘录递归算法，递归树变成光秃秃的树干咯，如下：
带备忘录的递归算法，子问题个数=树节点数=n，解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。接下来呢，我们用带备忘录的递归算法来解决这个青蛙跳阶问题的递归超时问题，代码如下：
自顶向下的动态规划步骤：
1）穷举分析、2）确定最优子结构、3）确定状态转移方程、4）确定边界、5）确定重叠子问题
总结：
带备忘录的递归解法就是自顶向下的动态规划，是从 f(10) 往 f(1) 方向延伸求解，也就是从大问题向子问题方向求解，减少重复计算，时间复杂度为 O(n)。
（2）自底向上的动态规划自顶向下的备忘录法使用了递归，计算 fib(10) 的时候最后还是要计算出 fib(1)、fib(2)、fib(3)…，那么何不先计算出 fib(1)、fib(2)，、ib(3)…呢？这就是自底向上动态规划的核心，先计算子问题，再由子问题计算父问题。
我们来看下自底向上的解法，从 f(1) 往 f(10) 方向，一个 for 循环就可以解决，如下：
带备忘录的递归解法，空间复杂度是 O(n)，但是仔细观察上图，可以发现，f(n) 只依赖前面两个数，所以只需要两个变量a和b来存储，就可以满足需求了，因此空间复杂度是O(1)就可以。
自底向上的动态规划实现代码如下：
自底向上的动态规划结题思路：
穷举分析；
确定边界；
找规律，确定最优子结构；
写出状态转移方程；
1）穷举分析
2）确定边界
3）找规律，确定最优子结构
4）写出状态转移方程
自底向上的递归代码实现模板
两种方式总结
一般来说由于备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销；使用自底向上的动态规划方法只使用循环和常数个空间，要比备忘录方法好。
5、动态规划的经典模型（1）线性模型
线性模型的是动态规划中最常用的模型，这里的线性指的是状态的排布是呈线性的。
（2）区间模型
区间模型的状态表示一般为 d[i][j]，表示区间 [i, j] 上的最优解，然后通过状态转移计算出 [i+1, j] 或者 [i, j+1] 上的最优解，逐步扩大区间的范围，最终求得 [1, len] 的最优解。
（3）树形模型
（4）背包模型
三、LeetCode 例题