第34天，动态规划part02，牢记五部曲步骤，编程语言：C++
目录
62.不同路径
63.不同路径II
343.整数拆分
96.不同的二叉搜索树
总结
62.不同路径
文档讲解：代码随想录不同路径
视频讲解：手撕不同路径
题目：
学习：本题最直观的是使用图论的深度搜索的方法，来枚举出来有多少种路径，总时间复杂度为O(2^(m + n - 1) - 1)，时间复杂度是非常大的，在力扣中是超时的。因此本题可以采取动态规划的方法来降低时间复杂度。
使用动态规划方法，可以从动态五部曲入手。
1.确定dp数组以及下标含义：本题类似于一个二维棋盘，因此我们可以设置一个二维dp数组，dp[i][j]，就表示为到达i行j列位置的路径总数。
2.确定递推公式：依据题干我们知道到达i行j列，我们只能从i-1行j列，和i行j-1列到达。因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
3.dp数组的初始化：首先依据题干我们可以知道到达第一行各点的路径数量都为1， 也即一直往右走，到达第一列各点的路径数量同理也都为1，因此我们对第一行和第一列进行初始化。
4.确定遍历顺序，依据递推公式我们可以确定每个点都是从其上方和左方推导而来的，因此我们从左到右一层一层遍历即可。
5.距离推导dp数组：
代码：
//时间复杂度O(m*n)
//空间复杂度O(m*n)
class Solution {
public:
int uniquePaths(int m, int n) {
//1.确定dp数组和下标含义
vector<vector<int>> dp(m, vector<int>(n, 0));//其中dp[i][j]表示到达i行j列共有多少条不同的路径
//2.确定递推公式
//由于每次只能向下或者向右，因此dp[i][j] = dp[i-1][j] + dp[i][j-1]
//3.初始化dp数组，由递推公式可知，我们应该初始化所有i=0和j=0的位置，同时，根据题干我们也能知道这些位置都是1
for(int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for(int j = 0; j < n; j++) {
dp[0][j] = 1;
}
//4.确定遍历顺序，可知每个点都是从其上方和左方推导而来的，因此我们需要从上至下，从左至右进行遍历
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
//5.打印dp数组
//cout << dp[i][j] << endl; //调试的时候使用
}
return dp[m - 1][n - 1];
}
};本题还可以通过数论来进行求解，由题意可知，我们无论如何都是要走m+n-2步才能到达终点的，其中由m-1步是要往下走的，不同路径就取决于这m-1步什么时候走，因此通过排列组合能够推出，总共的取法为Cm+n-2(上标m-1）。
代码：使用数论最关键的是防止两个int相乘出现溢出的情况，因此我们需要在计算分子的时候，不断除以分母。
//时间复杂度O(m)
//空间复杂度O(1)
class Solution {
public:
int uniquePaths(int m, int n) {
long long numerator = 1; // 分子
int denominator = m - 1; // 分母
int count = m - 1;
int t = m + n - 2;
while (count--) {
numerator *= (t--);
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return numerator;
}
};63.不同路径II
文档讲解：代码随想录不同路径II
视频讲解：手撕不同路径
题目：
学习：本题与上一题不同在于存在障碍物，因此我们需要对障碍物进行单独处理。从动态五部曲出发：
1.确定dp数组：与上一题一样，设置二维dp数组，dp[i][j]表示从起始点出发，到达（i，j)的不同路径数量。
2.确定递推公式：递推公式与上一题一样，但是要注意障碍物单独处理，也即有障碍物的地方就不用再进行赋值了（初始为0)
if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}3.dp数组初始化：同样也是第一行，第一列为1，但是要注意如果第一行出现障碍物，或者第一列出现障碍物，后面的格子就到达不了了，就不进行1的赋值了。（因为只能往下和右走，不能绕路)
4.确定遍历顺序，遍历顺序与上一题相同。
代码：
//时间复杂度O(n*m)
//空间复杂度O(m)
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;
//1.确定dp数组及下标含义
//dp[i][j]就表示到达i行j列有的路径数量
vector<vector<int>> dp(m,vector<int>(n, 0));
//2.确定递推公式
//dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，但是要注意如果obstacleGrid[i][j]处有障碍物，则不进行赋值
//3.初始化dp数组，也是需要赋值第一行和第一列，不同的在于如果第一行或者第一列上有障碍物，则后面的都无法到达，为0
for(int i = 0; i < m; i++) {
if(obstacleGrid[i][0] == 1) break; //遇到障碍物，后面的都无法抵达，保持为0
dp[i][0] = 1;
}
for(int j = 0; j < n; j++) {
if(obstacleGrid[0][j] == 1) break;
dp[0][j] = 1;
}
//4.确定遍历顺序，从上至下，从左至右
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) { //不是障碍物时再进行赋值
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
};343.整数拆分
文档讲解：代码随想录整数拆分
视频讲解：手撕整数拆分
题目：
学习：本题难点在于找到递推公式，也即找到数与数之间的关系。以动规五部曲来说。
1.确定dp数组以及下标的含义，依据题意我们可以设置一个一维的dp数组，dp[i]就表示为n = i时，乘积的最大值。
2.确定递推公式：我们需要思考dp[i]的最大值该如何得到，对于比i小的数来说，例如dp[i - 1],dp[i - 2]，它们分别表示了对i - 1拆分后乘积能够得到的最大值，以及对i - 2拆分后乘积能够得到的最大值，相较于i，它们之间就差一个差值，也即dp[i] 有可能会是 1*dp[i -1]也有可能会是2*dp[i-2]以此类推，这是获得dp[i]的一个途径。其次我们知道1*dp[i-1]中的dp[i-1]是对i-1进行整数拆分后得到的最大乘积，因此我们还错过了1*(i-1)的可能，虽然一般来说1*dp[i-1]是大于1*(i-1)的，但不保证中间不会有更大的情况出现。综上我们可以得出递推公式为：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
3.dp数组的初始化：要注意对于0和1来说，实际上是拆分不了的，因为题干要求了，至少拆分为2个数，且n>=2，因此我们这里对dp[2]进行初始化，dp[2]=1；
4.确定遍历顺序：显然我们需要依靠dp[i - j]的状态，所以i一定要从前往后遍历。
5.举例推导dp数组：
代码：
class Solution {
public:
int integerBreak(int n) {
//1.确定dp数组以及下标的含义
vector<int> dp(n + 1); //dp[i]表示n=i时的最大乘积
//2.确定递推公式：dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j) 对j进行遍历
//3.初始化dp数组：dp[0]和dp[1]都没有意义
dp[2] = 1;
//4.确定遍历顺序，外层需要对i进行从小到达遍历进行赋值，内层对j进行遍历，找到最大值
for(int i = 3; i < n + 1; i++) {
for(int j = 1; j <= i - 2; j++) { //最多取到i -
dp[i] = max(dp[i], max(j*(i - j), j*dp[i - j]));//max只能同时比较两个数
}
}
return dp[n];
}
};代码：可以对j的范围进行优化，根据数论，对一个数进行拆分，尽可能拆成相同的数最后得到会是最大的，因为a+b >= 2根号(ab)，因此要ab最大，就是取等于号的时候，此时a = b。
//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
public:
int integerBreak(int n) {
//1.确定dp数组以及下标的含义
vector<int> dp(n + 1); //dp[i]表示n=i时的最大乘积
//2.确定递推公式：dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j) 对j进行遍历
//3.初始化dp数组：dp[0]和dp[1]都没有意义
dp[2] = 1;
//4.确定遍历顺序，外层需要对i进行从小到达遍历进行赋值，内层对j进行遍历，找到最大值
for(int i = 3; i < n + 1; i++) {
for(int j = 1; j <= i/2; j++) { //最多取到i -
dp[i] = max(dp[i], max(j*(i - j), j*dp[i - j]));//max只能同时比较两个数
}
}
return dp[n];
}
};96.不同的二叉搜索树
文档讲解：代码随想录不同的二叉搜索树
视频讲解：手撕不同的二叉搜索树
题目：
学习：本题同样找到递推公式是关键，依据动规五部曲我们进行分析。
1.确定dp数组以及下标含义：在这里我们需要找到给定节点个数，能够得到的二叉搜索树种数。因此我们可以创建一个一维dp数组，dp[i]就表示i个节点能够得到的二叉搜索树种数。
2.确定递推公式：我们从n=1和n=2来看，对于n=1来说显然只有一棵二叉搜索树，n=2则有两棵二叉搜索树。
n=3时，则有5棵二叉搜索树
分析n=3的情况，当1为头节点时，实际上左子树节点数为0，右子树节点数为2，因此右子树共有n=2种可能。当2为头节点时，左子树节点数为1，右子树节点数为1，因此左右子树都是n=1种可能，乘起来就是1种可能。当3为头节点，左子树节点数为2，右子树节点数为0，因此左子树共有n=2种可能，右子树只有1种可能，乘起来就是2种可能。以此我们可以得出一个公式：dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]。由此我们可以推出：dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]。
所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量。
3.dp数组初始化：空节点实际上也可以作为一棵树包括空节点，左子树为空，右子树为空的情况，因此需要进行初始化dp[0] = 1，对于1个节点也能够通过dp[0]推出。
4.确定遍历顺序：从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
5.举例推导dp数组：
代码：
//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
public:
int numTrees(int n) {
//1.确定dp数组以及下标含义
vector<int> dp(n + 1); //dp[i] 表示i个节点能够组成的二叉搜索树的种类
//2.确定递推公式：dp[i] += dp[j - 1] * dp[i - j] //对j进行遍历
//3.初始化dp数组：由于空节点实际上也是一颗二叉树，，因此需要初始化
dp[0] = 1;
//dp[1] = 1; //可以进行初始化，也可以通过dp[0]推导而来
//4.确定遍历顺序，从小到大进行遍历
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j <= i; j++) {
dp[i] += dp[j - 1]*dp[i - j];
}
}
return dp[n];
}
};总结
做动态规划一定要牢记，动规五部曲。推导递推公式时，最重要的是从简单的往复杂的推，逐一分析找到关系。
