package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/unique-paths/
 */
public class Problem62 {
    public int uniquePaths(int m, int n) {
        Map<String, Integer> memo = new HashMap<>();
        return uniquePaths(m, n, 1, 1, memo);
    }

    private int uniquePaths(int m, int n, int x, int y, Map<String, Integer> memo) {
        if (x > m || y > n) {
            return 0;
        }
        if (x == m && y == n) {
            return 1;
        }
        if (memo.containsKey(x + "|" + y)) {
            return memo.get(x + "|" + y);
        }
        int a = uniquePaths(m, n, x + 1, y, memo);
        int b = uniquePaths(m, n, x, y + 1, memo);
        int result = a + b;
        memo.put(x + "|" + y, result);
        return result;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -143,35 +143,427 @@
         
-Map%3CString,
+int%5B%5D%5B%5D dp = new int%5Bm%5D%5Bn%5D;%0A        for (int i = 0; i %3C m; i++) %7B%0A            for (int j = 0; j %3C n; j++) %7B%0A                if (i == 0 %7C%7C j == 0) %7B%0A                    dp%5Bi%5D%5Bj%5D = 1;%0A                %7D else %7B%0A                    dp%5Bi%5D%5Bj%5D = dp%5Bi - 1%5D%5Bj%5D + dp%5Bi%5D%5Bj - 1%5D;%0A                %7D%0A            %7D%0A        %7D%0A        return dp%5Bm - 1%5D%5Bn - 1%5D;%0A    %7D%0A%0A//    public int uniquePaths(int m, int n) %7B%0A//       
  Integer
 %3E memo =
@@ -550,25 +550,28 @@
      Integer
-%3E
+%5B%5D%5B%5D
  memo = new 
@@ -574,21 +574,33 @@
 new 
-HashMap%3C%3E();%0A
+Integer%5Bm + 1%5D%5Bn + 1%5D;%0A//
     
@@ -641,23 +641,29 @@
  memo);%0A
+//
     %7D%0A
-%0A
+//%0A//
     priv
@@ -713,28 +713,16 @@
 t y,
- Map%3CString,
  Integer
 %3E me
@@ -717,17 +717,20 @@
  Integer
-%3E
+%5B%5D%5B%5D
  memo) %7B
@@ -726,24 +726,26 @@
 %5D%5B%5D memo) %7B%0A
+//
         if (
@@ -758,24 +758,26 @@
 %7C%7C y %3E n) %7B%0A
+//
             
@@ -786,16 +786,18 @@
 turn 0;%0A
+//
         
@@ -790,32 +790,34 @@
  0;%0A//        %7D%0A
+//
         if (x ==
@@ -828,24 +828,26 @@
 & y == n) %7B%0A
+//
             
@@ -852,24 +852,26 @@
   return 1;%0A
+//
         %7D%0A  
@@ -860,32 +860,34 @@
  1;%0A//        %7D%0A
+//
         if (memo
@@ -890,37 +890,28 @@
 memo
-.containsKey(x + %22%7C%22 + y)
+%5Bx%5D%5By%5D != null
 ) %7B%0A
+//
     
@@ -933,27 +933,18 @@
 memo
-.get(x + %22%7C%22 + y);%0A
+%5Bx%5D%5By%5D;%0A//
     
@@ -941,32 +941,34 @@
 y%5D;%0A//        %7D%0A
+//
         int a = 
@@ -994,32 +994,34 @@
  + 1, y, memo);%0A
+//
         int b = 
@@ -1055,16 +1055,18 @@
  memo);%0A
+//
         
@@ -1085,16 +1085,18 @@
  a + b;%0A
+//
         
@@ -1103,35 +1103,27 @@
 memo
-.put(x + %22%7C%22 + y,
+%5Bx%5D%5By%5D =
  result
-)
 ;%0A
+//
     
@@ -1141,16 +1141,18 @@
 result;%0A
+//
     %7D%0A%7D%0A

Update problem 62