动态规划算法介绍：就是解决获取最优解值的算法
- 1.动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
- 2.动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
- 3.与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)
- 4.动态规划可以通过填表的方式来逐步推进，得到最优解.
### 动态规划与分治算法的区别：
### 大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了
分治算法的每个子问题求解都是互相独立的；
动态规划算法则是：下一个子阶段求解是建立在上一个子阶段求解的基础上；
# 也就是说 ①把问题转换成子问题; ②并缓存中间结果；
1.递归求解，暴力解，容易超时；
打家劫舍问题，就是0-1背包问题 要么选要么不选；我们用递归解决：
递归三部曲:
- 选择递归函数的参数：一般就是选择随着递归状态而改变的的变量；
- 递归出口
- 递归方向
2.采用动态规划优化递归
动态规划的一般思路：
- basecase 就是递归出口；
- 状态转移方程就是 递推公式
- 缓存中间结果；题目用数组我们就用数组，一维数组用一维数组缓存；二维数组用二维数组缓存；
- 顺序，我们必须是知道前一个结果才能知道后一个；
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
1. 确定dp数组（也可能是二维） 以及下标的含义 2. 确定递推公式 最优子结构 3. dp数组如何初始化 dp[0] dp[1]等 4. 确定遍历顺序 从前往后还是从后往前 5. 举例推导dp数组 看看是否和题目描述的一致
e g： 1 .斐波那契数列 我们不用递归 用动态规划来做
题目描述：斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
动规五部曲：
这里我们要用一个一维dp数组来保存递归的结果
1. 确定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数组打印出来看看和我们推导的数列是不是一致的。
public static int fib(int n) {
//特殊情况
if (n<=1){
return n;
}
int[] dp=new int[n+1];
//初始化dp数组
dp[0]=0;
dp[1]=1;
for (int i = 2; i <dp.length ; i++) {
dp[i]=dp[i-1]+dp[i-2];//递推公式
}
return dp[n];
}
e g： 2 .爬楼梯
1. 确定dp数组以及下标的含义
dp[i]： 爬到第i层楼梯，有dp[i]种方法
2. 确定递推公式
如果可以推出dp[i]呢？从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。
## 注：在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。
这体现出确定dp数组以及下标的含义的重要性！
3. dp数组如何初始化
在回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]中方法。那么i为0，dp[i]应该是多少呢，题目中说了n是一个正整数，题目根本就没说n有为0的情况。所以本题其实就不应该讨论dp[0]的初始化！
我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。
所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
4. 确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
5. 举例推导dp数组 举例当n为5的时候，dp table（dp数组）应该是这样的
1 2 3 5 8
1 2 3 4 5
数组下标是1开始的
public static int climbStairs(int n) {
if (n<=2){
return n;
}
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
e g： 3.整数拆分
- 两种情况：
dp[i]代表要拆的整数i能得到的最大成绩
1.整数 i 拆成 j 和 i-j ， i-j 不再拆分，直接求乘积；乘积为 j* (i-j)
2.整数 i 拆成 j 和 i-j ， i-j 继续作为一个新的整数进行拆分，j* dp[i-j]
递推公式（状态转移方程）就是：
- dp[i] = max{dp[i], max((i - j) * j, dp[i - j] * j)};
那么在取最大值的时候，为什么还要比较dp[i]呢？
因为在递推公式推导的过程中，每次都会计算得出dp[i]，我们最后要取最大。
public static int integerBreak(int n) {
//dp[i] 为正整数 i 拆分后的结果的最大乘积
int[]dp=new int[n+1];
dp[2]=1;
//i是从2开始拆的
for(int i=2;i<=n;i++){
//j的范围是1到i-j
for(int j=1;j<=i-j;j++){
dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
