1
class Solution {
2
  public int uniquePaths(int m, int n) {
3
    int[][] dp = new int[m][n];
4

5
    for (int i = 0; i < m; i++) {
6
      for (int j = 0; j < n; j++) {
7
        dp[i][j] = -1;
8
      }
9
    }
10

11
    return helper(m, 0, n, 0, dp);
12
  }
13

14
  private int helper(int m, int i, int n, int j, int[][] dp) {
15
    if (i == m || j == n) {
16
      return 0;
17
    }
18

19
    if (i == m - 1 && j == n - 1) {
20
      dp[i][j] = 1;
21
    }
22

23
    if (dp[i][j] == -1) {
24
      dp[i][j] = helper(m, i + 1, n, j, dp) + helper(m, i, n, j + 1, dp);
25
    }
26

27
    return dp[i][j];
28
  }
29
}