Unique Paths II

1package pkg5leetcode.official75;2 3/*4 * Unique Paths II | LC 635 * APPROACH: DP paths to cell avoiding obstacles.6 * COMPLEXITY: Time O(mn), Space O(n)7 */8public class official75_LC63UniquePathsII {9    static int uniquePathsWithObstacles(int[][] grid) {10        int m = grid.length, n = grid[0].length;11        if (grid[0][0] == 1) return 0;12        int[] dp = new int[n];13        dp[0] = 1;14        for (int i = 0; i < m; i++)15            for (int j = 0; j < n; j++)16                if (grid[i][j] == 1) dp[j] = 0;17                else if (j > 0) dp[j] += dp[j - 1];18        return dp[n - 1];19    }20 21    public static void main(String[] args) {22        check(uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}) == 2, "case1");23        check(uniquePathsWithObstacles(new int[][]{{0,1},{0,0}}) == 1, "case2");24        System.out.println("all tests passed");25    }26 27    static void check(boolean cond, String name) {28        if (!cond) throw new AssertionError("FAILED: " + name);29        System.out.println("  PASS " + name);30    }31}