力扣 - 63题 不同路径 II (C++) - dp

题目链接:https://leetcode.cn/problems/unique-paths-ii/
题目如下:

class Solution {
public:
    int uniquePathsWithObstacles(vector>& obstacleGrid) {
        //重要!! 相比62题没有障碍的情况;有障碍就是标记对应的dp table（dp数组）保持初始值(0)
        int m=obstacleGrid.size();
        if(m==0) return 0;
        int n=obstacleGrid[0].size();
        vector> dp(m,vector(n,0));

        //若(i, 0)这条边有了障碍之后，则障碍之后（包括障碍）都是走不到的位置
        for(int i=0;i
            if(obstacleGrid[i][0]==0) dp[i][0]=1;
            else break;
        }
        for(int j=0;j
            if(obstacleGrid[0][j]==0) dp[0][j]=1;
            else break;
        }

        for(int i=1;i
            for(int j=1;j

                if(obstacleGrid[i][j]==1) continue;//有障碍,则之后的位置都不能到达

                dp[i][j]=dp[i-1][j]+dp[i][j-1];//状态转换方程,相比没有障碍的,只需加个判断
                
            }
        }

        return dp[m-1][n-1];
    }
};