美文网首页
63. Unique Paths II

63. Unique Paths II

作者: Al73r | 来源:发表于2017-10-16 12:07 被阅读0次

    题目

    Follow up for "Unique Paths":

    Now consider if some obstacles are added to the grids. How many unique paths would there be?

    An obstacle and empty space is marked as 1 and 0 respectively in the grid.

    For example,
    There is one obstacle in the middle of a 3x3 grid as illustrated below.

    [
    [0,0,0],
    [0,1,0],
    [0,0,0]
    ]
    The total number of unique paths is 2.

    分析

    和第62题基本一样,不同的是在初始化时要将障碍处的路径数置为0,且在推导的时候跳过这些位置。
    而且也要推导最后两行。

    实现

    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            if(obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
            int m=obstacleGrid.size(), n=obstacleGrid[0].size();
            int dp[m][n];
            dp[m-1][n-1] = 1;
            for(int i=0; i<m; i++)
                for(int j=0; j<n; j++)
                    if(obstacleGrid[i][j])
                        dp[i][j] = 0;
            for(int i=m-2; i>=0; i--)
                if(!obstacleGrid[i][n-1]) dp[i][n-1] = dp[i+1][n-1];
            for(int i=n-2; i>=0; i--)
                if(!obstacleGrid[m-1][i]) dp[m-1][i] = dp[m-1][i+1];
            for(int i=m-2; i>=0; i--)
                for(int j=n-2; j>=0; j--)
                    if(!obstacleGrid[i][j])
                        dp[i][j] = dp[i+1][j] + dp[i][j+1];
            return dp[0][0];
        }
    };
    

    思考

    做这种题的时候要非常注意,条件增加时变化了的情况。如果继续沿用之前的那种初始化最后一行和最后一列为1的情况就会出现问题,改成由后一个推导才可。

    相关文章

      网友评论

          本文标题:63. Unique Paths II

          本文链接:https://www.haomeiwen.com/subject/nvrkuxtx.html