动态规划（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]; } };
相信到这里，大家已经基本对动态规划有了大致了解，接下来可以安心开刷了( •̀ ω •́ )✧
题目：
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、动态规划理论基础
