题解 | #不同路径的数目(二)#

2022.0906算法第56题不同路径的数目(二)

这道题对于做过不同路径的数目一，思路还是能够想到的

主要就是需要注意两点

1、初始化的时候，如果遇到障碍0的时候，0后面的数据都没法到达，需要赋值为0

2、当状态矩阵在进行递推时，如果遇到障碍0，则直接将该位置赋值为0，其余的情况不变依然时左边和上边相加

int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
    //状态矩阵，和网格的大小一致，表示到达i，j位置的路径数
    vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),0));
    //初始化第一列，每个位置只有一条路，遇到0则直接跳出，后面还为0
    for(int i=0;i<obstacleGrid.size();i++){
        if(obstacleGrid[i][0]==0){
            break;
        } 
        dp[i][0]=1;           
    }
    //初始化第一行，每个位置赋值为1，遇到0则直接跳出
    for(int i=0;i<obstacleGrid[0].size();i++){            
        if(obstacleGrid[0][i]==0){
            break;
        }  
        dp[0][i]=1;
    }
    //循环状态矩阵，网格路径计算
    for(int i=1;i<obstacleGrid.size();i++){
        for(int j=1;j<obstacleGrid[0].size();j++){
            //遇到障碍时，直接赋值0，无法到达
            if(obstacleGrid[i][j]==0){
                dp[i][j]=0;
                //cout<<dp[i][j]<<endl;
            }
            //否则此位置还是等于左边和上班两个位置的路径数相加
            else{
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                //cout<<dp[i][j]<<endl;
            }
        }
    }
    //返回路径数
    return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
}