针对动态规划问题，我总结了以下5步：
确定dp数组以及下标的含义；
递推公式；
dp数组如何初始化；
遍历顺序；
打印dp数组（用来debug）；
以上5步适用于任何动态规划问题，下面针对题目，我们来具体实践：
说明：本题代码均为力扣AC代码。
题目一：斐波那契数
class Solution {
public:
int fib(int n) {
//1.dp[i]表示第i个斐波那契数的值
//2.递推公式 dp[i] = dp[i-1] + dp[i-2]
//3.dp[0] = 0 dp[1] = 1
//4.遍历顺序：本题从前到后遍历即可
if(n == 0 || n == 1)return n;
vector<int>dp(n+1);
dp[0] = 0;
dp[1] = 1;
for(int i = 2;i <= n;++i)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];//返回第n个斐波那契数的值
}
};当然，本题非常简单，不使用动态规划也是OK的。
class Solution {
public:
int fib(int n) {
//迭代
if(n == 0 || n== 1)return n;
vector<int>f(n+1);
f[0] = 0;
f[1] = 1;
int cur = 0;
for(int i = 2;i <= n;++i)
{
cur = f[0] + f[1];
f[0] = f[1];
f[1] = cur;
}
return cur;
}
};题目二：爬楼梯
分析一波：为啥递推公式是dp[i] = dp[i-1]+dp[i-2]？dp[i]为到达第i阶有dp[i]种方法，.dp[i-1]为到达第i-1阶有dp[i-1]种方法，.dp[i-2]为到达第i-2阶有dp[i-2]种方法，要想到达第i阶，只需从第i-1阶爬一阶或者从第i-2阶爬二阶即可，所以dp[i] = dp[i-1]+dp[i-2]。
class Solution {
public:
int climbStairs(int n) {
//1.dp[i]为到达第i阶有dp[i]种方法
//2.递推公式：dp[i] = dp[i-1]+dp[i-2]
//3.dp[1] = 1,dp[2] = 2
//遍历顺序：因为dp[i]依赖于dp[i-1]、dp[i-2]，所以应该从前到后遍历
vector<int> dp(n + 1);
if(n == 1 || n == 2)return n;
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=n;++i)
{
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];//爬到第n阶一共有多少种方法
}
};题目三： 使用最小花费爬楼梯
分析一波：本题和上一道爬楼梯很相似，不过是加上了个花费，这里dp[i]为到达i阶楼梯最小的花费，要想到达第i阶，只需从第i-1阶爬一阶或者从第i-2阶爬二阶即可，从第i-1阶爬到第i阶需要花费dp[i-1]+cost[i-1],从第i-2阶爬到第i阶需要花费dp[i-2]+cost[i-2],本题要求最小花费，所以状态转移方程为dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]).
对于初始化，本题说了可以选择从下标为0或1的元素作为初始阶梯，还要注意一点是不跳不花费体力，所以dp[0] = 0,dp[1] = 0.
对于遍历顺序，由于dp[i]是依靠dp[i-1]和dp[i-2]推导的，所以遍历顺序是从前到后。
分析完以后，就能很丝滑的做出来啦！
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int>dp(n+1);
dp[0] = 0;
dp[1] = 0;
for(int i=2;i<=n;++i)
{
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};题目四：不同路径
分析一波：本题是二维矩阵，所以dp数组应该定义成二维的，dp[i][j]代表从(0,0)位置走到(i,j)位置有多少种不同的路径，可以看到，如果想到达(i,j)的位置，只能从(i,j-1)的位置走一步或者从(i-1,j)的位置向下走一步，所以dp[i][j] = dp[i][j-1]+dp[i-1][j].
对于初始化，要想到达(i,j)的位置，要么从上面过来，要么从左边过来，所以我们要把最左边和最上边都初始化，初始化成多少呢？本题要求只能向右或者向下走，所以最上面行从最左侧走到最右侧只有一种走法，最左侧的列中从最上到最下也只有一种走法，所以初始化如下图。
class Solution {
public:
int uniquePaths(int m, int n) {
//创建m行n列的二维数组
vector<vector<int>>dp(m,vector<int>(n));
for(int i=0;i<m;++i)dp[i][0] = 1;
for(int j=0;j<n;++j)dp[0][j] = 1;
for(int i=1;i<m;++i)
{
for(int j=1;j<n;++j)
{
dp[i][j] = dp[i][j-1]+dp[i-1][j];
}
}
return dp[m-1][n-1];
}
};题目五：不同路径II
本题和上一题类似，只是本题多了一个障碍物，对于状态转移方程，如果(i,j)位置有障碍的话，那么我们无法继续推导，所以我们需要添加一个条件就是当(i,j)位置不是障碍物时，我们进行推导，否则不去推导。对于初始化，和上一题不同的是，第一列如果有障碍物的话，障碍物后面的位置都无法到达，第一行也是如此，所以我们在初始化时应该加上一个条件，就是当前位置没有障碍物，我们才给dp[i][0]、dp[0][j]初始化成1.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)return 0;
//创建m行n列的二维数组
vector<vector<int>>dp(m,vector<int>(n));
//dp数组初始化
for(int i = 0;i < m && obstacleGrid[i][0] == 0;++i)dp[i][0] = 1;
for(int j = 0;j < n && obstacleGrid[0][j] == 0;++j)dp[0][j] = 1;
for(int i = 1;i < m;++i)
{
for(int j = 1;j < n;j++)
{
if(!obstacleGrid[i][j])
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};题目六：整数拆分
1.确定dp数组含义：dp[i]表示将i进行拆分后得到最大的乘积
2.确定递推公式：将i拆分成两个数最大积为j*(i-j)，拆分成三个及以上为j*dp[i-j]，这里有个问题，为什么j不拆？实际上，在我们拆分 dp[i-j] 过程中已经包含了拆分 j 的情况，所以这里只考虑如何对 i-j 进行拆分即可，所以递推公式为dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))
3.dp数组如何初始化？根据dp数组含义，dp[0] = 0,dp[1] = 0,dp[2] = 1
4.遍历顺序：根据递推公式可以看出，dp[i]的状态依靠dp[i-j]的状态，所以是从前到后遍历。
class Solution {
public:
int integerBreak(int n) {
if(n == 0 || n == 1)return 0;
if(n == 2)return 1;
vector<int>dp(n+1);
dp[0] = 0,dp[1] = 0,dp[2] = 1;
for(int i=3;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];
}
};对于本题，可以做一个小小的优化。对于拆分i使之乘积最大，一定是拆分成m个近似相同的子数才能得到最大乘积。只不过m我们不知道是几，但是可以确定的是m一定大于等于2，所以在判断条件中，只需要 j <= i/2 即可。举个例子，拆分10的话，可以拆分成5*5，也可以拆分成3*3*4，如果拆分成6*4，后续无论对4如何拆分都不可能得到最大的，因为我们要把i拆分成近似相同的子数才能得到最大值。
题目七：
1.明确dp数组及下标含义：1到i为节点的二叉搜索树的个数为dp[i]
2.递推公式：根据图中分析，dp[3]就是以元素1为头结点BST的数量+以元素2为头结点BST的数量+以元素3为头结点BST的数量，我们要计算dp[i],只需要让 j 从遍历 1 到 i，计算 j 为头结点对应BST的个数并将他们相加即可。注意，j为头结点时，其左子树数目为 j-1 个，右子树数目为 i-j 个状态转移方程：dp[i] += dp[j-1]*dp[i-j].
3.如何初始化？dp[0] = 1,因为空BST也是BST
4.遍历顺序：从前到后
class Solution {
public:
int numTrees(int n) {
if(n == 1)return 1;
vector<int>dp(n+1);
dp[0] = 1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=i;++j)
{
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
};
