Unique Paths II

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 3x3 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.

Naive Way: 在算法上修改。这是Unique Path 的算法。

public class Solution {
    public int uniquePaths(int m, int n) {
        int opt[][] = new int[m][n];
        // base case
        for(int i = 0;i < m;i++) opt[i][0] = 1;
        for(int j = 0;j < n;j++) opt[0][j] = 1;
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                opt[i][j] = opt[i-1][j] + opt[i][j-1];
        return opt[m-1][n-1];
    }
}


如果当前有障碍物，那么就要置0，所以新逻辑是
opt[i][0] = matrix[i][0] ==0?0:opt[i-1][0];
opt[0][j] = matrix[0][j]==0?0:opt[0][j-1];
opt[i][j] = matrix[i][j]==0?0:opt[i-1][j]+opt[i][j-1];

算法复杂度为O(nm), space O(nm)。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m==0) return 0;
        int n = obstacleGrid[0].length;
        
        int opt[][] = new int[m][n];
        // base case
        opt[0][0] = obstacleGrid[0][0]==1?0:1;
        for(int i = 1;i < m;i++) opt[i][0] = obstacleGrid[i][0]==1?0:opt[i-1][0];
        for(int j = 1;j < n;j++) opt[0][j] = obstacleGrid[0][j]==1?0:opt[0][j-1];
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                opt[i][j] = obstacleGrid[i][j]==1?0:(opt[i-1][j] + opt[i][j-1]);
        return opt[m-1][n-1]; 
    }
}

对应的，写出简化space的形式。这里有一点和之前不一样是i=0也要写进循环，它对应单一一行的情况，因为之前没有障碍，一行就是1，现在还要判断一下是否有障碍，

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m==0) return 0;
        int n = obstacleGrid[0].length;
        int row[] = new int[m];
        // base case
        for(int i = 0;i < m;i++) row[i] = obstacleGrid[i][0]==1?0:(i==0?1:row[i-1]);
        // iteration
        for(int j = 1;j < n;j++)
            for(int i = 0;i < m;i++)
                row[i] = obstacleGrid[i][j]==1?0:((i==0 || obstacleGrid[i-1][j]==1?0:row[i-1]) + (obstacleGrid[i][j-1]==1?0:row[i]));
        return row[m-1]; 
    }
}

附上之前的代码方便对照：

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m > n) return uniquePaths(n,m);
        int row[] = new int[m];
        // base case
        for(int i = 0;i < m;i++) row[i] = 1;
        // ieration
        for(int j = 1;j < n;j++)
            for(int i = 1;i < m;i++)
                row[i] = row[i] + row[i-1];
        return row[m-1];
    }
}

还有就是为了达到 O(min(m,n))的space，应该要比较一下n和m，取较小的做数组。


Improved Way: 这道题跟之前有一个很大的不同在于，输入参数有一个m-by-n的数组，如果可以破坏这个数组，就可以利用原来的数组存opt而不需要额外的空间。

space O(1)

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m==0) return 0;
        int n = obstacleGrid[0].length;
        
        // base case
        obstacleGrid[0][0] = obstacleGrid[0][0]==1?0:1;
        for(int i = 1;i < m;i++) obstacleGrid[i][0] = obstacleGrid[i][0]==1?0:obstacleGrid[i-1][0];
        for(int j = 1;j < n;j++) obstacleGrid[0][j] = obstacleGrid[0][j]==1?0:obstacleGrid[0][j-1];
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                obstacleGrid[i][j] = obstacleGrid[i][j]==1?0:(obstacleGrid[i-1][j] + obstacleGrid[i][j-1]);
        return obstacleGrid[m-1][n-1]; 
    }
}