Introduction
The Unique Paths problem is one of the most important Grid Dynamic Programming interview questions.
You are given:
m rows
n columns A robot starts at:
Top Left Cell Goal:
Reach Bottom Right Cell Allowed Moves:
Move Right or Move DownFind:
Total number of unique paths. Example
m = 3
n = 7
Output = 28 Key Observation
To reach any cell:
(i,j) Robot can come from:
Top Cell (i-1,j) or Left Cell (i,j-1) Therefore:
dp[i][j] = dp[i-1][j] + dp[i][j-1]This is the DP recurrence.
Approach 1 : Memoization
Explanation
Use recursion and store results.
Steps:
- Solve smaller states.
- Save answers.
- Reuse computations.
- Avoid repeated work.
Approach 2 : Tabulation
Explanation
Build DP table from top-left to bottom-right.
Base Case:
First Row = 1First Column = 1
Because:
Only one way to reach them. Transition:
dp[i][j] = dp[i-1][j] + dp[i][j-1] Dry Run
Input:
m = 3n = 3DP Table:
1 1 1
1 2 31 3 6
Answer:
6 Approach 3 : Space Optimized DP
Explanation
Instead of storing:
m × n table Store only:
Current Row This reduces space complexity.
Practice
Complexity Analysis
Memoization
Time Complexity: O(m × n)
Space Complexity: O(m × n)
Tabulation
Time Complexity: O(m × n)
Space Complexity: O(m × n)
Space Optimized DP Time Complexity: O(m × n)Space Complexity: O(n)
Why This Problem is Important
This problem teaches:
- 2D Dynamic Programming
- Grid Traversal
- State Transitions
- Space Optimization
- Matrix DP
Common Beginner Mistakes
- Wrong base cases
- Incorrect indexing
- Using recursion only
- Not initializing first row
- Not initializing first column
Interview Tip
Always explain:
Current Cell = Top Cell + Left Cell This is the foundation of most:
Grid DP ProblemsRelated Questions
- Minimum Path Sum
- Dungeon Game
- Cherry Pickup
- Unique Paths II
- Edit Distance
Final Takeaway
Unique Paths is the best starting point for learning 2D Dynamic Programming.
It teaches:
- Grid DP
- State transitions
- Matrix traversal
- Space optimization
Mastering this problem makes advanced 2D DP questions significantly easier to solve.