动态规划，英文：Dynamic Programming，简称DP，是一种把原问题分解为相对简单的子问题，并保存子问题的解以避免重复计算，从而高效求解复杂问题的方法。
同样是解决小问题得到大问题的解，前面学习过有相同性质的算法包括：递推、贪心、搜索。
1、每个阶段只有一个状态->递推
2、每个阶段直接选择局部最优的，没有状态推导->贪心
3、每个阶段的最优状态是由之前所有阶段的状态的组合得到->搜索
4、每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到->动态规划
基本概念
最优子结构
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到，当前问题的最优解包含了子问题的最优解。
子问题重叠
就是求解过程中每次产生的子问题并不总是新问题，有大量子问题是重复的。
状态转移方程
每次得到的解即状态
从上一状态解=>下一状态解 称为：状态转移
通俗解释
动态规划问题的一般形式就是求最值。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。
1.虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的状态转移方程，才能正确地穷举。
2.你需要判断算法问题是否具备最优子结构，是否能够通过子问题的最值得到原问题的最值。
3.动态规划问题存在重叠子问题，如果暴力穷举的话效率会很低，所以需要你使用DP 数组来优化穷举过程，避免不必要的计算。
解题步骤
1.确定DP数组以及下标的含义
2.确定状态转移方程(递推公式)
3.DP数组如何初始化
4.确定遍历顺序
5.举例推导、打印DP数组
代码框架
// 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
//此时的状态已经因为做了选择而改变
result = 求最值(result, dp(状态1, 状态2, ...))
return result
//自底向上迭代的动态规划
//初始化
dp[0][0][...] = 初始值
//进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
入门举例
简单题目是用来加深对解题方法论理解的。
1.斐波那契数列
这里我们要用一个一维dp数组来保存递归的结果
- 确定dp数组以及下标的含义
dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2.确定递推公式
递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
3.dp数组如何初始化
dp[0] = 0;
dp[1] = 1;
4.确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。
const int N=1e5;
int f[N];
int fib(int n){
f[1]=0,f[2]=1;
for(int i=3;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
递归解法
int dp[1005];
int fib(int n){
if(n==1) return 0;
if(n==2) return 1;
//已经计算过，不用再计算了
if(dp[n]) return dp[n];
//在返回结果之前，存入备忘录
dp[n]=fib(n-1)+fib(n-2);
return dp[n];
}
2.最大子段和
给一个长度为n的整数序列a,选出其中连续且非空的一段，使这段的和最大。
例如：对于 6 -1 5 4 -7,最长的子段和为14，是6+(-1)+5+4
- 确定dp数组以及下标的含义
dp[i]的定义为：从开始位置到第i个的斐波那契数值是dp[i]
2.确定递推公式
dp数组表示从开始位置和当前位置为结尾的最大子段和
动态规划如何调试
写动规题目，代码出问题很正常！
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
一些同学对于dp的学习是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。
这是一个很不好的习惯！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。
看题解之前，可以自己先思考这三个问题：
这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？
如果这灵魂三问自己都做到了，基本上这道题目也就解决了