代码随想录算法训练营第三十九天|62.不同路径 63. 不同路径 II 343.整数拆分 96.不同的二叉搜索树

本文主要是介绍代码随想录算法训练营第三十九天|62.不同路径 63. 不同路径 II 343.整数拆分 96.不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode 62.不同路径

题目链接：62.不同路径

踩坑：二维的vector数组需要初始化，否则会报错访问空指针

思路：

确定动态数组的含义：dp[i][j]：到达（i，j）有多少条路经
递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化动态数组：dp[0][0] = 1
遍历顺序：从左到右，从上到下

代码：

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));dp[0][0] = 1;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(i-1 >=0 && j-1 >= 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];else if(i-1 < 0 && j-1 >= 0) dp[i][j] = dp[i][j-1];else if(i-1 >= 0 && j-1 < 0) dp[i][j] = dp[i-1][j];}}return dp[m-1][n-1];}
};

LeetCode 63. 不同路径 II

题目链接：63. 不同路径 II

踩坑：无

思路：障碍物网格的可达路径为0

确定动态数组的含义：dp[i][j]：到达（i，j）有多少条路经
递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化动态数组：dp[0][0] = 1
遍历顺序：从左到右，从上到下

代码：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));dp[0][0] = 1;for(int i = 0; i < obstacleGrid.size(); i++){for(int j = 0; j < obstacleGrid[0].size(); j++){if(obstacleGrid[i][j] == 1){dp[i][j] = 0;continue;}if(i-1 >= 0 && j-1 >= 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];else if(i-1 >= 0 && j-1 < 0) dp[i][j] = dp[i-1][j];else if(i-1 < 0 && j-1 >= 0) dp[i][j] = dp[i][j-1];}}return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];}
};

LeetCode 343.整数拆分

题目链接：343.整数拆分

踩坑：max函数只能有两个参数

思路：

动态数组的含义：dp[i]：将 i 拆分后的最大乘积
递推公式(需要遍历 j )：如果分成两份dp[i] = j * (i-j)，如果分成多份dp[i] = j * (d[i-j])
初始化动态数组：dp[0] = 0; dp[1] = 0; dp[2] = 1
遍历顺序：从小到大

代码：

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1, 0);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(max(j*(i-j), j*dp[i-j]), dp[i]);}}return dp[n];}
};

LeetCode 96.不同的二叉搜索树

题目链接：96.不同的二叉搜索树

踩坑：看到二叉树就有点怕，直接看视频了

思路：

动态数组的含义：dp[i]：{1…i }一共有多少个不同的二叉搜索树
递推公式：用dp[i]举例，当1做根节点，其左子树有0个节点，右子树有i-1个节点，分别对应dp[0],dp[i-1]，则一共有dp[0]*dp[i-1]种情况。所以需要遍历所有可能做根节点的数。
初始化动态数组：dp[0] = 1; dp[1] = 1
遍历顺序：从小到大

代码：

class Solution {
public:int numTrees(int n) {vector<int> dp(n+1, 0);dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){for(int j = 1; j <= i; j++){dp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
};