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)