LC 0062 [M] Unique Paths - ALawliet/algorithms GitHub Wiki

start from the bottom right with right and down padding, the num paths of the current cell is the sum of the num paths of the cells to the right and down

because we can either go right or down, we can prefill the 0th row and col with 1s

each cell represents the num paths to get to the end from that cell

i prefer backwardsPadding because it makes the follow-up (if there are obstacles) easier by just adding 2 if statements and seems more commonly ideal for "DP in a grid from start to end" problems

class Solution:
    def uniquePaths(self, n_cols: int, n_rows: int) -> int:
        T = [ [0 for _ in range(n_cols)] for _ in range(n_rows) ]
        
        T[0][0] = 1
        for r in range(1, n_rows):
            T[r][0] = 1
        for c in range(1, n_cols):
            T[0][c] = 1

        for r in range(1, n_rows):
            for c in range(1, n_cols):
                T[r][c] = T[r-1][c] + T[r][c-1]
            
        return T[-1][-1]

class Solution:
    def uniquePaths(self, n_cols: int, n_rows: int) -> int:
        T = [ [0 for _ in range(n_cols + 1)] for _ in range(n_rows + 1) ]

        T[n_rows-1][n_cols-1] = 1

        for r in range(n_rows - 1, -1, -1):
            for c in range(n_cols - 1, -1, -1):
                T[r][c] += T[r+1][c] + T[r][c+1]

        return T[0][0]

T/S: O(n_rows * n_cols)