【Leetcode】63. 不同路径 II

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                res[j] += res[j - 1];
                System.out.println("i=" + i + "_" + "j=" + j + ":" + Arrays.toString(res));
            }
        }
        return res[n - 1];
    }
}

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

class Solution(object):
    def uniquePathsWithObstacles(self, Grid):
        """
        :type Grid: List[List[int]]
        :rtype: int
        """
        m, n = len(Grid), len(Grid[0]) if Grid else 0
        res = [1] + [0] * (n - 1)
        for i in range(m):
            for j in range(n):
                if Grid[i][j] > 0:
                    res[j] = 0
                elif j > 0:
                    res[j] += res[j - 1]
                print(str(i) + '-' + str(j) + ":" + str(res))
        return res[-1]

x = [
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
    ]

i=0  j=0:[1, 0, 0]
i=0  j=1:[1, 1, 0]
i=0  j=2:[1, 1, 1]
i=1  j=0:[1, 1, 1]
i=1  j=1:[1, 0, 1]
i=1  j=2:[1, 0, 1]
i=2  j=0:[1, 0, 1]
i=2  j=1:[1, 1, 1]
i=2  j=2:[1, 1, 2]