网站开发使用的软件,大连网站开发公司电话,wordpress如何上传mp3,做网站有高手没有代码随想录算法训练营第四十二天
62.不同路径
题目链接#xff1a;62.不同路径
确定dp数组以及下标的含义#xff1a;到[i,j]点位有dp[i,j]条路径确定递推公式#xff1a;每个点位都可以从它上面一个位置或者左边一个位置到达#xff0c;所以路径数量等于上面位置的路径…代码随想录算法训练营第四十二天
62.不同路径
题目链接62.不同路径
确定dp数组以及下标的含义到[i,j]点位有dp[i,j]条路径确定递推公式每个点位都可以从它上面一个位置或者左边一个位置到达所以路径数量等于上面位置的路径数量左边位置的路径数量dp[i,j] dp[i][j-1]dp[i-1][j]dp数组如何初始化dp[i,0]和dp[j,0]都等于1确定遍历顺序从左上往右下遍历打印dp数组。
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m,vectorint(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;im;i){for(int j 1;jn;j){dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};63. 不同路径 II
题目链接63. 不同路径 II
确定dp数组以及下标的含义到[i,j]点位有dp[i,j]条路径确定递推公式每个点位都可以从它上面一个位置或者左边一个位置到达所以路径数量等于上面位置的路径数量左边位置的路径数量dp[i,j] dp[i][j-1]dp[i-1][j],终点有障碍物的话到这个点的路径数量就是0dp数组如何初始化dp[i,0]和dp[j,0]都等于1如果最上面一行和最左面一排有障碍物那障碍物后方可达的路径就全都是0了确定遍历顺序从左上往右下遍历打印dp数组。
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if(obstacleGrid[m-1][n-1]1||obstacleGrid[0][0] 1)return 0;vectorvectorint dp(m,vectorint(n,0));for (int i 0; i m; i) {if(obstacleGrid[i][0]1)break;dp[i][0] 1;}for (int j 0; j n; j) {if(obstacleGrid[0][j]1)break;dp[0][j] 1;}for(int i 1;im;i){for(int j 1;jn;j){if(obstacleGrid[i][j]1)dp[i][j] 0;else dp[i][j] dp[i-1][j]dp[i][j-1];coutdp[i][j]endl;}}return dp[m-1][n-1];}
};
