Unique Paths in Grid
You'll learn how to count all distinct routes through a grid using dynamic programming.
Imagine you're standing at the top-left corner of a city grid and need to reach the bottom-right corner. You can only move right or down (never left or up). How many different routes can you take?
The Core Idea
Given an m x n grid, you start at position (0, 0) and want to reach (m-1, n-1). At each cell, you have at most two choices: move right or move down. The problem asks: how many unique paths exist?
This is a classic dynamic programming problem because:
- Optimal substructure: The number of ways to reach any cell depends on the number of ways to reach the cells directly above it and to its left
- Overlapping subproblems: We'll recompute paths to the same cells multiple times if we use naive recursion
The DP Approach
Define dp[i][j] = number of unique paths to reach cell (i, j).
Base cases:
dp[0][j] = 1for all columns (only one way: keep moving right)dp[i][0] = 1for all rows (only one way: keep moving down)
Transition:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
You can reach cell (i, j) either from the cell above or from the cell to the left, so you add those possibilities.
Think of it like water flowing down: each cell accumulates all the paths that can flow into it from above and from the left.
Key Takeaway: The Unique Paths problem uses dynamic programming to efficiently count routes by recognizing that paths to any cell equal the sum of paths to its top and left neighbors.