动态规划-基础
动态规划（Dynamic Programming，简称DP）是一种算法思想，它将问题分解为更小的子问题，然后将子问题的解存起来，避免重复计算。
所以动态规划中每一个状态都是由上一个状态推导出来的，这一点就区别于贪心，贪心没有状态推导。
并且动态规划问题可以分为很多种类，如线性DP、区间DP、背包DP、树形DP、状态压缩DP、数位DP、计数型DP、递推型DP、博弈型DP和记忆化搜索等。每种类型都有其特定的问题模型和解决方法。如线性DP通常通过处理一维数组或字符串，区间DP处理二维区间，背包问题处理物品的选择问题。
这说的的都是啥玩意啊？怎么字都认识？连在一起，就都不懂了？
我们来看下，网上比较流行的一个例子：
- A ： "1+1+1+1+1+1+1+1 =？"
- A ： "上面等式的值是多少"
- B ： 计算 "8"
- A : 在上面等式的左边写上 "1+" 呢？
- A : "此时等式的值为多少"
- B : 很快得出答案 "9"
- A : "你怎么这么快就知道答案了"
- A : "只要在8的基础上加1就行了"
- A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"
有一道题，挺适合启蒙思想的-青蛙跳阶问题
这里我们只是带入思想，不给出题解，相信大家，在看完本文后，肯定能解决。
leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。
- 要想跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去;要么是先跳到第8级，然后一次迈2级台阶上去。
- 同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去;要么是先跳到第7级，然后一次迈2级台阶上去。
- 要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去;要么是先跳到第6级，然后一次迈2级台阶上去。
所以可以推导，得出这么一个结论：
f（10） = f（9）+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)
...
f(3) = f(2) + f(1)
f(n) = f(n-1) + f(n-2)而 f(n) = f(n-1) + f(n-2); 又叫做递推公式，这也是动态规划的核心。
Carl对动态规划，总结成了5步，如果这5步都能合理的掌握并运用，相当于神功大成\(￣︶￣*\))
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
好啦，接下来举例子：
斐波那契数
斐波那契数 （通常用
F(n)表示）形成的序列称为 斐波那契数列 。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定
n，请计算F(n)。示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3提示：
0 <= n <= 30
这道题目，作例子，再合适不过了。
在示例1~3中：递归公式，给的在明显不过了。
f(n) = f(n-1) + f(n-2)；
咱们在开篇时已经讲过：动态规划是 将问题分解为更小的子问题，然后将子问题的解存起来，避免重复计算。
重点是存起来，所以就需要用到数组喽，如下：
arr[0]=0;
arr[1]=1;
for(int i=2; i<=n; ++i){
arr[i]=arr[i-1]+arr[i-2];
}这就是递推，本题的总代码如下：
class Solution {
public:
int fib(int n) {
// 排除意外
if(n==0) return 0;
else if(n==1) return 1;
vector<int> arr(n+1);
arr[0]=0;
arr[1]=1;
for(int i=2; i<=n; ++i){
arr[i]=arr[i-1]+arr[i-2];
}
return arr[n];
}
};相信到这里，大家已经基本对动态规划有了大致了解，接下来可以安心开刷了( •̀ ω •́ )✧
题目：
2、爬楼梯-（解析）-线性dp入门
3、使用最小花费爬楼梯-（解析）-线性dp入门
4、不同路径-（解析）-区间dp入门
5、不同路径 II-（解析）-区间dp入门
6、整数拆分-（解析）-需要考虑，数字拆成几个？需要有一定推理能力
7、不同的二叉搜索树-（解析）-需要有能力，跳出数字约束，进入宏观层面
2、爬楼梯
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶提示：
1 <= n <= 45
class Solution {
// 线性dp基础练习
public:
int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
vector<int> res(n+1);
res[1]=1;
res[2]=2;
for(int i=3; i<=n; ++i){
res[i] = res[i-1] + res[i-2];
}
return res[n];
}
};3、使用最小花费爬楼梯
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为
0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
class Solution {
// 稍稍具有一点，推导能力的线性dp
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> res(cost.size()+1);
res[0] = 0;
res[1] = 0;
for(int i=2; i<=cost.size(); ++i){
res[i] = min(res[i-1]+cost[i-1], res[i-2]+cost[i-2]);
}
return res[cost.size()];
}
};4、不同路径
一个机器人位于一个
m x n网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下示例 3：
输入：m = 7, n = 3 输出：28示例 4：
输入：m = 3, n = 3 输出：6提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
class Solution {
// 入门的区间dp
public:
int uniquePaths(int m, int n) {
vector<vector<int>> res(m,vector<int>(n));
for(int i=0; i<n; ++i) res[0][i]=1;
for(int j=0; j<m; ++j) res[j][0]=1;
for(int i=1; i<m; ++i){
for(int j=1; j<n; ++j){
res[i][j]=res[i-1][j]+res[i][j-1];
}
}
return res[m-1][n-1];
}
};5、不同路径 II
给定一个
m x n的整数数组grid。一个机器人初始位于 左上角（即grid[0][0]）。机器人尝试移动到 右下角（即grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。网格中的障碍物和空位置分别用
1和0来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于
2 * 109。示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有2条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
class Solution {
// 入门的区间dp
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<int>> res(row,vector<int>(col, 0));
for(int i=0; i<row; ++i){
if(obstacleGrid[i][0]==1) break;
res[i][0] = 1;
}
for(int i=0; i<col; ++i){
if(obstacleGrid[0][i]==1) break;
res[0][i] = 1;
}
for(int i=1; i<row; ++i){
for(int j=1; j<col; ++j){
if(obstacleGrid[i][j]==1) continue;
res[i][j] = res[i-1][j] + res[i][j-1];
}
}
return res[row-1][col-1];
}
};6、整数拆分
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。提示:
2 <= n <= 58
class Solution {
// 本题的思考角度在于，一个数字，能被拆几次。（2~n此，因为拆的次数多了，所以才有无限可能...
public:
int integerBreak(int n) {
vector<int> dp(n+1, 0);
dp[0] = dp[1]=0;
for(int i=2; i<=n; ++i){
for(int j=1; j<i; ++j){
dp[i] = max(dp[i], max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
};7、不同的二叉搜索树
给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。示例 1：
输入：n = 3 输出：5示例 2：
输入：n = 1 输出：1提示：
1 <= n <= 19
class Solution {
// 实现宏观抽象，不要看具体的数据，跳过数据看规律。
public:
int numTrees(int n) {
vector<int> dp(n+1,0);
dp[0]=1;
for(int i=1; i<=n; ++i){
for(int j=0; j<i; ++j){
dp[i] += dp[i-1-j]*dp[j];
}
}
// for(int i : dp) cout<<i<<endl;
return dp[n];
}
};需要有，跳出数据，从宏观逻辑分析的能力。
借鉴博客：
1、动态规划理论基础
2、看一遍就理解：动态规划详解