63.不同路径 II

原题链接

题解

一个简单的动态规划，除了第0行、第0列和障碍物之外的点，都是由他的上一个点和左边的一个点拓展而来
所以当该点是障碍物：令dp[i][j] = 0(方便后面直接运算)
当该点是（0,0）且不是障碍：dp[0][0] = 1;
当该点是第0行的点：令dp[i][j] = dp[i][j - 1]
当该点是第0列的点：令dp[i][j] = dp[i - 1][j]
反之dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

代码如下

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int lenx = obstacleGrid.length; if(lenx == 0) return 0;
        int leny = obstacleGrid[0].length;

        int[][] dp = new int[101][101];
        if(obstacleGrid[0][0] == 0)//当起点是障碍物的时候，就不能走了，直接起点为0（后面就会全为0，因为所有的点都是通过起点拓展出来的）
        dp[0][0] = 1;
        for(int i = 0; i < lenx; ++i){
            for(int j = 0; j < leny; ++j){
                if(obstacleGrid[i][j] == 0){
                    if(i - 1 >= 0) dp[i][j] += dp[i - 1][j];
                    if(j - 1 >= 0) dp[i][j] += dp[i][j - 1];
                }
            }
        }

        return dp[lenx - 1][leny - 1];
    }
}