dynamic programming
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
写在前面
计算机归根结底只会做一件事：穷举。
所有的算法都是在让计算机【如何聪明地穷举】而已，动态规划也是如此。
动态规划与递归
动态规划是自底向上，递归树是自顶向下
为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
啥叫「自顶向下」？
注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「自顶向下」
int Fibonacci(size_t n)
{
if(n == 1 || n == 2)
{
return n;
}
return Fibonacci1(n-1) + Fibonacci1(n-2);
}
ps: 大家应该还记得，递归的实现看起来很优雅，实际上有很大的限制。计算的数值稍微大一点，基本上是算不出来的。
啥叫「自底向上」？
反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
// 动态规划法计算斐波那契数列
int fib(int N) {
vector<int> dp(N + 1, 0);
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}
状态转移方程
这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
可见列出「状态转移方程」的重要性，它是解决问题的核心。
很容易发现，其实状态转移方程直接代表着暴力解法。
千万不要看不起暴力破解，动态规划问题最困难的就是写出状态转移方程，
便于理解的例子
题目
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从上到下选择一条路，使得经过的数字之和最大。
路径上的每一步只能往左下或者右下走。
递归解法
可以看出每走第n行第m列时有两种后续:向下或者向右下
由于最后一行可以确定,当做边界条件,所以我们自然而然想到递归求解
class Solution{
public int getMax(){
int MAX = 101;
int[][] D = new int[MAX][MAX]; //存储数字三角形
int n; //n表示层数
int i = 0; int j = 0;
int maxSum = getMaxSum(D,n,i,j);
return maxSum;
}
public int getMaxSum(int[][] D,int n,int i,int j){
if(i == n){
return D[i][j];
}
int x = getMaxSum(D,n,i+1,j);
int y = getMaxSum(D,n,i+1,j+1);
return Math.max(x,y)+D[i][j];
}
}
重复计算
其实仔细观察,上面的解答过程时间复杂度难以想象的大,那是因为他对有的数字的解进行了多次的重复计算,具体如下图:
括号中代表计算次数，默认为 1 次。
7
3 8
8 1(2) 0
2 7(3) 4(3) 4
4 5(4) 2(6) 6(4) 5
如果不明白上图,可以把每条路径都画出来,观察每个数字有多少条路径经过了他,就会一目了然
然后我们就可以自然而然的想到,如果我们每次都把结果保存下来,复杂度就会大大降低。
ps: 这里就是动态规划最核心的思想。
动态规划解法
核心代码部分。
for(int i = n-1; i >= 1; i--) {
for(int j = 1; j <= i; j++>) {
maxSum[i][j] = Math.max(maxSum[i+1][j], maxSum[i+1][j+1]);
}
}
其实,仔细观察该解题过程,该过程就是标准的动态规划解题过程,如果把该过程画出来(找到每一步的最优解,其他的舍弃)对动态规划会有更深刻的解法
分类
动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等；
应用实例：
最短路径问题 ，项目管理，网络流优化等；
概念意义
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。
例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
概念引入
多阶段决策过程的最优化问题。
含有递推的思想以及各种数学原理（加法原理，乘法原理等等）。
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。
当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）
这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。
基本思想
动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
我们可以用一个表来记录所有已解的子问题的答案。
不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
具体的动态规划算法多种多样，但它们具有相同的填表格式。
参考资料
https://www.jianshu.com/p/40064cb0d5f3
