Number of Robot Paths - Dynamic Programming / Grid

Problems
1

https://algo.monster/problems/robot_unique_path

3

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];
}
5

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]
7

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)
8

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?

9

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)

10

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)
11

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.

12

Solution with less space complexity: O(m)

# Space complexity: O(m)
def unique_paths(m: int, n: int) -> int:
    column = [1]*m
    
    for c in range(1, n):
        for r in range(1, m):
            column[i] += column[i-1]           
            
    return column[-1]