package leetcode;

/**
 * https://leetcode.com/problems/unique-paths-ii/
 */
public class Problem63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0) {
            return 0;
        }
        return findPaths(obstacleGrid, obstacleGrid.length-1, obstacleGrid[0].length-1,
            0, 0);
    }
    
    private int findPaths(int[][] grid, int destRow, int destCol, int row, int col) {
        if (row == destRow && col == destCol) {
            return 1;
        } 
        if (row > destRow || col > destCol) {
            return 0;
        }
        if (grid[row][col] == 1) {
            return 0;
        }
        int a = findPaths(grid, destRow, destCol, row+1, col);
        int b = findPaths(grid, destRow, destCol, row, col+1);
        return a + b;
    }
    
    public static void main(String[] args) {
        Problem63 prob = new Problem63();
        int[][] grid = new int[][]{
            new int[]{0, 0, 0},
            new int[]{0, 1, 0},
            new int[]{0, 0, 0},
            new int[]{0, 0, 0},
            new int[]{0, 0, 0},
        };
        System.out.println(prob.uniquePathsWithObstacles(grid));
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -272,32 +272,85 @@
 rn 0;%0A        %7D%0A
+        Map%3CString, Integer%3E memo = new HashMap%3C%3E();%0A
         return f
@@ -437,16 +437,22 @@
     0, 0
+, memo
 );%0A    %7D
@@ -539,16 +539,51 @@
  int col
+,%0A        Map%3CString, Integer%3E memo
 ) %7B%0A    
@@ -594,18 +594,17 @@
 if (row 
-==
+%3E
  destRow
@@ -608,17 +608,16 @@
 Row 
-&&
+%7C%7C
  col 
-==
+%3E
  des
@@ -643,17 +643,84 @@
  return 
-1
+0;%0A        %7D%0A        if (grid%5Brow%5D%5Bcol%5D == 1) %7B%0A            return 0
 ;%0A      
@@ -722,17 +722,16 @@
        %7D
- 
 %0A       
@@ -731,33 +731,34 @@
         if (row 
-%3E
+==
  destRow %7C%7C col 
@@ -746,32 +746,33 @@
  == destRow 
-%7C%7C
+&&
  col 
-%3E
+==
  destCol) %7B%0A
@@ -782,33 +782,33 @@
          return 
-0
+1
 ;%0A        %7D%0A    
@@ -811,39 +811,79 @@
         
-if (grid%5Brow%5D%5Bcol%5D == 1
+String key = row + %22%7C%22 + col;%0A        if (memo.containsKey(key)
 ) %7B%0A    
@@ -889,33 +889,45 @@
          return 
-0
+memo.get(key)
 ;%0A        %7D%0A    
@@ -982,16 +982,22 @@
 w+1, col
+, memo
 );%0A     
@@ -1055,401 +1055,97 @@
 ol+1
-);%0A        return a + b;%0A    %7D%0A    %0A    public static void main(String%5B%5D args) %7B%0A        Problem63 prob = new Problem63();%0A        int%5B%5D%5B%5D grid = new int%5B%5D%5B%5D%7B%0A            new int%5B%5D%7B0, 0, 0%7D,%0A            new int%5B%5D%7B0, 1, 0%7D,%0A            new int%5B%5D%7B0, 0, 0%7D,%0A            new int%5B%5D%7B0, 0, 0%7D,%0A            new int%5B%5D%7B0, 0, 0%7D,%0A        %7D;%0A        System.out.println(prob.uniquePathsWithObstacles(grid))
+, memo);%0A        int result = a + b;%0A        memo.put(key, result);%0A        return result
 ;%0A  

Solve problem 63