1
#define vi vector<int>
2
#define vvi vector<vi>
3
class Solution {
4
 public:
5
  int countPath(vvi &dp, int r, int c, int m, int n) {
6
    if (m == r - 1 || n == c - 1) return 1;
7

8
    if (dp[m][n] != -1) return dp[m][n];
9

10
    return dp[m][n] = countPath(dp, r, c, m + 1, n) + countPath(dp, r, c, m, n + 1);
11
  }
12
  int uniquePaths(int m, int n) {
13
    vvi dp(m, vi(n, -1));
14

15
    return countPath(dp, m, n, 0, 0);
16
  }
17
};