前两题自己AC的，后两题确实有点难，看讲解才AC的，中规中矩吧。

62.不同路径

这个主要是需要先把第0行和第0列初始化，全都赋值为1，然后从坐标（1，1）开始遍历，每一个格子的走法只取决于该格子正上方和左边相邻各自的走法数，将两者相加即可，感觉有点像爬楼梯的思路了。

class Solution {
public:int uniquePaths(int m, int n) {//1.确定dp[i][j]的含义：爬到坐标为(i, j)的所有方法数//2.确定递推公式  dp[i][j] = dp[i - 1][j] + dp[i][j - 1]//3.dp数组初始化 dp[0][j] = 1, dp[i][0] = 1//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)vector<vector<int>> dp(m, vector<int>(n, 0));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 - 1][j] + dp[i][j - 1];}return dp[m - 1][n - 1];}
};

63. 不同路径 II

这道题比上一道题稍微难一点，这道题加入了障碍，有障碍的地方无法通行，因此在初始化第0行和第0列的时候，如果没有遇到障碍，则该处赋值为1，一旦遇到障碍，则障碍处及之后的格子全都赋值为0（无法通行，只能从另一边过来）。状态转移方程与上一题的一样。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//1.确定dp[i][j]的含义：爬到坐标为(i, j)的所有方法数//2.确定递推公式  dp[i][j] = dp[i - 1][j] + dp[i][j - 1]//3.dp数组初始化 dp[0][j] = 1, dp[i][0] = 1//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)int m = obstacleGrid.size();  //行int n = obstacleGrid[0].size(); //列vector<vector<int>> dp(m, vector<int>(n, 0));//第0列初始化for(int i = 0; i < m; i++){if(obstacleGrid[i][0] != 0) //遇到障碍break;else dp[i][0] = 1;}//第0行初始化for(int j = 0; j < n; j++){if(obstacleGrid[0][j] != 0) //遇到障碍break;else dp[0][j] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(obstacleGrid[i][j] != 1)  //该处没有障碍，可以到达dp[i][j] = dp[i - 1][j] + dp[i][j - 1];else dp[i][j] = 0;}}return dp[m - 1][n - 1];}
};

343. 整数拆分

这道题确实有点难了，尽管我知道要拆成尽可能相近的数相乘才能得到最大乘积，但是我不知道应该拆分成多少个数相乘才能使得乘积最大，导致无从下手。其实这道题明确了dp[i]的含义以后就很好办了，这道题目的dp[i]代表着拆分整数i所能得到的最大乘积，拆分i有两种拆法：1.拆成两个数相乘；2.拆成3个及以上的数相乘。拆成两个数的写法为j * (i - j)，而3个及以上的数相乘应该写成j * dp[i - j]（类似于递归了，dp[i - j]可以不断往下拆分），我觉得这个拆分是最难想到的。
遍历需要用二重循环，外层循环是遍历每一个i，每一层循环就能确定拆分i的最大乘积，内层循环用来遍历，维护拆分i的最大值，需要取j * (i - j),j * dp[i - j],和dp[i]的最大值。

class Solution {
public:int integerBreak(int n) {//1.确定dp[i]的含义：拆分整数i所能得到的最大乘积//2.确定递推公式  dp[i] = max(j * (i - j), j * dp[i - j], dp[i])//3.dp数组初始化 dp[0] = 0, dp[1] = 0, dp[2] = 1;//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)vector<int> dp(n + 1);dp[2] = 1;for(int i = 3; i <= n; i++)  //外循环确定拆分整数i所能得到的最大乘积for(int j = 1; j < i; j++) //内层循环用来遍历i的所有拆分情况dp[i] = max({j * (i - j), j * dp[i - j], dp[i]});return dp[n];}
};

96. 不同的二叉搜索树

这道题需要在循环中累加，不是简单的前几项相加。本题dp[i]的含义：输入为i时的所有可能的二叉搜索树的数量，而dp[i] = 1为根节点时的二叉树数量 + 2为根节点时的二叉树数量 +… + i为根节点时的二叉树数量，本题也是用二重循环来做，外层循环用来确定输入为i时的所有二叉树数量，而内层循环用来计算当输入为i且跟节点为j时的二叉树数量，并将结果加入到总数中。

class Solution {
public:int numTrees(int n) {//1.确定dp[i]的含义：输入为i时的所有可能的二叉搜索树的数量//2.确定递推公式  dp[i] = dp[j - 1] * dp[i - j] //(左子树有j - 1个节点，右子树有i - j个节点，0 <= j <= i)//3.dp数组初始化 dp[0] = 1;//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)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]; }
};