Unique Paths
The Unique Paths problem asks how many unique paths a robot can take from the top-left to the bottom-right of a grid, moving only down or right.
READY
0
1
2
0
1
2
Initialize 3x3 grid with 0s
Next
Base Case: dp[0][0] = 1 (Only 1 way to reach border)
Rows
Cols
Intuition
The robot can only arrive at cell (i, j) from either the cell above it (i-1, j) or the cell to its left (i, j-1). Therefore, the number of ways to reach (i, j) is simply the sum of the ways to reach those two neighbors.
Concept
2D Dynamic Programming:
We define dp[i][j] as the number of unique paths to reach cell (i, j).
Recurrence:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Base Cases:
- First Row: Always 1 way (move purely right).
- First Column: Always 1 way (move purely down).
How it Works
Algorithm:
- Initialize a 2D array
dpof size m × n. - Fill the first row and first column with 1s.
- Iterate through the rest of the grid:
- For each cell (i, j), set dp[i][j] = dp[i-1][j] + dp[i][j-1].
- The result is the value in the bottom-right corner dp[m-1][n-1].
Step-by-Step Breakdown
Visualizing the grid filling:
- Initialization: The top and left borders are filled with 1.
- Propagation: The internal cells are filled by summing the values from the top and left.
- Result: The values accumulate towards the bottom-right.
When to Use
Applications:
- Pathfinding in grids with constrained movement.
- Game theory (counting winning states).
- Robotics (counting valid trajectories).
When NOT to Use
- Unconstrained Movement: If 4-directional movement is allowed, this simple DP fails (cycles possible). Use BFS/DFS.
- Obstacles: Requires conditional checks (if cell is obstacle, ways = 0).
How to Identify
"Grid", "Move down/right", "Count paths".
Applying for software engineering roles? Free, no sign-up: