LeetCode题目:Unique Paths II,二维动态规划

By | 2012 年 11 月 5 日

每个cell,如果自身没有障碍的话,可以从上面一个cell或者左边一个cell到达。所以用动态规划来解决很简单:
开一个数组(和输入矩阵的列数等大),记录到达该cell的可能路径个数。
逐行扫描输入矩阵,根据条件计算到达该cell可能的路径个数(只能从上面或者左边)。
最后输出这个数组的最后一个元素即可。

这样做的话,时间复杂度是O(rows * cols),空间复杂度是O(cols)



Unique Paths II
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 3×3 grid as illustrated below.

 [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
 

The total number of unique paths is 2.
Note: m and n will be at most 100.



代码:24ms过大集合

class Solution {
public:
    int uniquePathsWithObstacles(vector > &obstacleGrid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = obstacleGrid.size();
        if(rows == 0) return 0;
        int cols = obstacleGrid[0].size();
        if(cols == 0) return 0;
        int *preways = new int[cols];
        int *ways = new int[cols];
        
        //first row
        preways[0] = 1 - obstacleGrid[0][0];
        for(int i = 1; i  &rowobs = obstacleGrid[ir];
            for(int ic = 0; ic < cols; ++ic) {
                if(rowobs[ic] == 1) {
                    ways[ic] = 0;
                    continue;
                }
                //from cell above
                ways[ic] = preways[ic];
                //from left
                if(ic > 0) {
                    ways[ic] += ways[ic - 1];
                }
            }
            int *temp = preways;
            preways = ways;
            ways = temp;
        }
        return preways[cols-1];
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注