My simple top-down approach in java

```
public static int uniquePaths(int m, int n) {
int[][] memo = new int[m+1][n+1];
return uniquePaths(m, n, memo);
}
private static int uniquePaths(int m, int n, int[][] memo) {
if( m < 1 || n < 1) return 0;
if (m == 1 || n == 1) return 1;
if (memo[m][n] == 0) {
memo[m][n] = uniquePaths(m - 1, n, memo) + uniquePaths(m, n - 1, memo);
}
return memo[m][n];
}
```

def unique_paths(m: int, n: int) → int:

res = [[1 for c in range(n)]for r in range(m)]

```
for y in range(1, m):
for x in range(1,n):
res[y][x] = res[y-1][x] + res[y][x-1]
return res[-1][-1]
```

I find it more intuitive to simply mark that there’s one path from all cells in either bottom or right edge, and calculate backwards from there with recursion:

def unique_paths(m: int, n: int) → int:

grid = [[0 for _ in range(n)] for _ in range(m)]

for row in range(m):

grid[row][-1] = 1

for col in range(n):

grid[-1][col] = 1

```
def calc_grid(row, col):
if grid[row][col] == 0:
grid[row][col] = calc_grid(row+1, col) + calc_grid(row, col+1)
return grid[row][col]
return calc_grid(0, 0)
```

I sometimes get confused if `dp`

initialization needs to be till `m`

, `n`

or `m+1`

, `n+1`

.

Can anyone explain if there is a way to always get this right?

You can calculate the answer directly.

from math import comb

def unique_paths(m: int, n: int) → int:

return comb(m+n-2, n-1)

The top-down solution would be as

```
def unique_paths(m: int, n: int) -> int:
def dfs(x, y, memo):
if x > m - 1 or y > n - 1:
return 0
if memo[x][y] != -1:
return memo[x][y]
if x == m - 1 and y == n -1:
return 1
result = dfs(x + 1, y, memo) + dfs(x, y + 1, memo)
memo[x][y] = result
return result
memo = [[-1 for _ in range(n)] for _ in range(m)]
return dfs(0, 0, memo)
```

That depends on your base case. For instance in the coin change 1 problem we initialize the dp table to n + 1 because we consider the base case of using no coins to get a sum of 0. This base case isn’t actually present in the coins list we are given like for coins = [1, 2, 5] to get a sum of 0 we need to include no coins, hence the dp is table is len(coins) + 1 and in our for loop we iterate from 1 → len(coins) + 1.