leecode第六十三题(不同路径 II)

leecode第六十三题(不同路径 II)

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        if(m==0)
            return 0;
        int n=obstacleGrid[0].size();
        
        vector<vector<long>> path(m,vector<long> (n,0));//建立一个二维数组
        
        for(int i=m-1;i>=0;i--)//从右下角到左上角遍历
        {
            for(int j=n-1;j>=0;j--)
            {
                if(obstacleGrid[i][j]==1)//如果是不能过的地方,直接给0
                {
                    path[i][j]=0;
                    continue;
                }
                if(i==m-1&&j==n-1)//特殊情况,终点给1
                {
                    path[i][j]=1;
                    continue;
                }
                
                long temp_down,temp_right;//考虑边界情况
                if(i==m-1)
                    temp_down=0;
                else 
                    temp_down=path[i+1][j];
                if(j==n-1)
                    temp_right=0;
                else
                    temp_right=path[i][j+1];
                
                path[i][j]=temp_down+temp_right;//动态规划,当前节点可能的路径等于下面和右面的节点路径可能之和
            }
        }
        return path[0][0];
    }
};

分析:

首先时那个long字型,因为有的案例步子太多了。第二就是那个

if(i==m-1&&j==n-1)//特殊情况,终点给1

这个给且不小心写成或了。

上一篇:leecode第五十五题(跳跃游戏)


下一篇:leecode-第二题-两数相加