Unique Paths
https://leetcode.com/problems/unique-paths/
Approach 1: Bottom-Up DP
Utilized the fact that there’s only one way to reach grids in the first row/column to avoid handling edge indices.
dp = [[1] * n for _ in range(m)]
for col in range(1, m):
for row in range(1, n):
dp[col][row] = dp[col - 1][row] + dp[col][row - 1]
return dp[m - 1][n - 1]Approach 2: Closed Form Expression
Total of (m - 1) + (n - 1) moves are needed, m - 1 of them are down, n - 1 of them are right. Therefore the result can be expressed as
from math import factorial
return factorial(m + n - 2) // factorial(n - 1) // factorial(m - 1)