Unique Paths
Calculate the number of possible unique paths for a robot to move from the top-left to the bottom-right of a grid, moving only down or right.
Ready
Rows
3
Cols
3
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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 `dp` of size m \times 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".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.