网页上做网会员网站备案怎么写,网站制作的电话,免费空间访客网站,玉林住房和城乡建设局网站官网62.不同路径 每次向右或者向下走两个选择#xff0c;定义dp数组dp[i][j] 为到达索引ij的路径和#xff0c;状态转移公式为 dp[i][j]dp[i-1][j]dp[i][j-1]#xff0c;初始状态的第一行和第一列为1#xff0c;从左上到右下开始遍历即可。详细代码如下#xff1a; class Sol… 62.不同路径 每次向右或者向下走两个选择定义dp数组dp[i][j] 为到达索引ij的路径和状态转移公式为 dp[i][j]dp[i-1][j]dp[i][j-1]初始状态的第一行和第一列为1从左上到右下开始遍历即可。详细代码如下 class Solution {
public:int uniquePaths(int m, int n) {vectorvectorintdp (m,vectorint(n,1));for(int i1;im;i){for(int j1;jn;j){dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
}; 为了优化空间复杂度可以用一个一维数组因为一定是先更新左边的值再更新右边的值。 详细代码如下 class Solution {
public:int uniquePaths(int m, int n) {vectorintdp (n,1);for(int i1;im;i){for(int j1;jn;j){dp[j]dp[j-1]; //当前dp为从上方路径来dp[j-1]为从左方来}}return dp[n-1];}
}; 63. 不同路径 II 这道题和上一道思路一样但是这道有障碍物需要注意有障碍物的索引到达该处的路径和为0根据这个条件增加处理逻辑即可整体的转移方程还是 详细代码如下 class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {if(obstacleGrid.empty()) return 0;vectorvectorintdp(obstacleGrid.size(),vectorint(obstacleGrid[0].size(),0));int m obstacleGrid.size();int n obstacleGrid[0].size();for(int i0;im;i){if(obstacleGrid[i][0]1||i0dp[i-1][0]0) dp[i][0]0;else dp[i][0] 1;}for(int j1;jn;j){if(obstacleGrid[0][j]1||dp[0][j-1]0) dp[0][j]0;else dp[0][j] 1;}for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]1) dp[i][j]0;else dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
}; 感觉这道题的优化空间版本细节有点多但还是附上代码 class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {if(obstacleGrid.empty()) return 0;int m obstacleGrid.size();int n obstacleGrid[0].size();vectorintdp (n,0);for(int j0;jn;j){if(obstacleGrid[0][j]1||j0dp[j-1]0) dp[j]0;else dp[j] 1;}for(int i1;im;i){for(int j0;jn;j){if(obstacleGrid[i][j]1) dp[j]0;else if(j0) dp[j] dp[j]dp[j-1];}}return dp[n-1];}
};
