Unique Paths II

https://leetcode.com/problems/unique-paths-ii/description/

Easy 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.

Thoughts

相比起I需要对有石头的地方特殊处理一下. 石头代表那个点无路可达，值为0. 需要特别注意的是当石头出现在首行或首列时，后面的路都不再可达。

给定M*N的矩阵G,

设Fi,j为从(0, 0)处往下或往右走到(i, j)处的unique path的数目, 当G(i, j) = 1时Fi,j = 0. 求F(M-1, N-1).

Code

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] f = new int[n];
        f[0] = 1;
        for (int[] row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 1) {
                    f[j] = 0;
                } else if (j > 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f[n - 1];
    }
}

Analysis

做题耗时: 10min

Errors:

1. 没有把首行或者首列石头后的置为0.

TC: O(mn)