62.不同路径 63.不同路径ii

题目:62. 不同路径 - 力扣（LeetCode）

思路:此题主要是理清思路，难度不大，注意初始化的是第一行和第一列

代码:

class Solution {
public:
    int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));  
    for(int i = 0;i < m;i++)dp[i][0] = 1;
    for(int i = 0;i < n;i++)dp[0][i] = 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 - 力扣（LeetCode）

思路:区别在于有障碍就不能走，注意点是在初始化的时候，遇到有障碍后续都走不通要为0，注意循环的跳出条件

 for(int i = 0 ;i < m && obstacleGrid[i][0] == 0; i++)//进行初始化
            dp[i][0] = 1;

第二，在递推公式的前提判断，如果当前位置就是障碍物，直接为跳过。 

代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();//行
        int n = obstacleGrid[0].size();//列
        if(obstacleGrid[m-1][n-1] == 1 ||obstacleGrid[0][0] == 1)
        return 0;
        vector<vector<int>>dp(m,vector(n,0));
        for(int i = 0 ;i < m && obstacleGrid[i][0] == 0; i++)//进行初始化
            dp[i][0] = 1;
        for(int j = 0 ;j < n && obstacleGrid[0][j] == 0; j++)//进行初始化
            dp[0][j] = 1;
        for(int i = 1 ;i < m ;i++)
        {
            for(int j = 1 ;j < n ;j++)
            {
                if(obstacleGrid[i][j] == 1)
                continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return  dp[m-1][n-1] ;
    }
};

原文地址：https://blog.csdn.net/zengxuan151168/article/details/143374215

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！