# Number of Robot Paths - Dynamic Programming / Grid

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.