代码随想录算法训练营第三十四天|leetcode62、63题

一、leetcode第62题

本题设置dp数组的含义为走到第i行第j列的路径数，由于只能向下或向右走一格，可得递推式dp[i][j]=dp[i-1][j]+dp[i][j-1]，还要对构建数组第一行和第一列进行初始化，因为只有一条路径可以到达。

具体代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
    vector<vector<int>>dp(m);
    for(int i=0;i<m;i++)
    {
        dp[i].resize(n);
    }
    dp[0][0]=1;
    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];
    }
};

二、leetcode第63题

本题与上题相比多了障碍物，在处理过程中要加入两个细节，第一个是初始化第一行和第一列时遇到障碍物要将障碍物后面的数dp值设为0，因为已经不可能到达；第二个是在使用递推式的时候遇到障碍物不再使用递推式而是直接将该值置为0。

具体代码如下：

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