Unique Paths and Minimum Path Sum on Grids
Fill a 2D DP table for unique paths with and without obstacles, then adapt it to minimise the sum of values along a path.
Unique Paths on a Grid
Unique Paths (LeetCode 62) asks: in an m×n grid, how many distinct paths go from the top-left corner to the bottom-right corner if you can only move right or down? For a 3×7 grid the answer is 28. The key insight is that every path to cell (i,j) must come from either (i-1,j) (above) or (i,j-1) (left), giving a natural 2D DP formulation.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 22D DP Table for Unique Paths
Define dp[i][j] = number of paths to cell (i,j). The first row and first column are all 1s (only one way to reach any cell in the top row or leftmost column). For other cells: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Fill the table row by row and the answer is dp[m-1][n-1]. Time complexity: O(m×n), space: O(m×n) reducible to O(n).
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP