Loading learning content...
In our exploration of dynamic programming, we've tackled problems where the state could be captured by a single index—Fibonacci, climbing stairs, house robber. These 1D DP problems form the foundation. But many real-world problems require tracking two independent variables simultaneously.
Consider navigating a city grid, comparing two strings character by character, or filling a knapsack where both item indices and remaining capacity matter. These problems demand a two-dimensional state space—and with it, a 2D DP table.
The jump from 1D to 2D DP is one of the most important conceptual leaps in algorithmic thinking. Once you master it, you unlock a vast array of problems in string processing, grid navigation, sequence alignment, and optimization.
By the end of this page, you will master the classic "Unique Paths" problem and its variants. You'll understand how to formulate 2D DP problems, visualize state transitions on a grid, and implement solutions that are both correct and efficient. This problem serves as the gateway to all 2D dynamic programming.
Problem Statement:
A robot is located at the top-left corner of an m × n grid. The robot can only move down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many unique paths are there to reach the destination?
Visualizing the Grid:
Imagine a 3×7 grid. The robot starts at position (0, 0) and must reach position (2, 6). At each cell, it can move right or down. The question is: in how many distinct ways can it reach the goal?
Why This Problem Matters:
The unique paths problem is deceptively simple yet profoundly instructive. It appears in:
More importantly, the thinking pattern you develop here transfers directly to harder problems: grid paths with obstacles, minimum path sum, longest common subsequence, and string edit distance.
We assume the grid has no obstacles (we'll add obstacles later). Movements are restricted to right and down only—no diagonal, up, or left movements. The grid dimensions m and n are positive integers, typically 1 ≤ m, n ≤ 100 for DP solutions, though combinatorial solutions handle much larger values.
Before diving into dynamic programming, let's develop intuition through recursion. This approach, while inefficient, reveals the problem's structure and exposes why DP is necessary.
Recursive Insight:
To reach cell (i, j), the robot must have come from either:
(i-1, j) (if it moved down)(i, j-1) (if it moved right)Therefore, the number of ways to reach (i, j) equals the sum of ways to reach (i-1, j) and (i, j-1).
Base Cases:
(0, 0), there's exactly 1 way to be there (do nothing)i < 0) or column index is negative (j < 0), there are 0 ways (we've gone off the grid)123456789101112131415161718192021222324252627
def unique_paths_recursive(m: int, n: int) -> int: """ Count unique paths in an m x n grid using naive recursion. Time Complexity: O(2^(m+n)) - exponential, highly inefficient Space Complexity: O(m + n) - recursion stack depth """ def count_paths(row: int, col: int) -> int: # Base case: Out of bounds if row < 0 or col < 0: return 0 # Base case: Starting cell if row == 0 and col == 0: return 1 # Recursive case: Sum paths from above and left paths_from_above = count_paths(row - 1, col) paths_from_left = count_paths(row, col - 1) return paths_from_above + paths_from_left # Start from bottom-right corner (m-1, n-1) return count_paths(m - 1, n - 1) # Example: 3x7 gridprint(unique_paths_recursive(3, 7)) # Output: 28The Problem: Exponential Time Complexity
This recursive solution works but is catastrophically slow. For a modest 20×20 grid, it would make over 137 billion function calls!
The issue is overlapping subproblems. Consider a 3×3 grid. To compute paths to (2, 2), we need paths to (1, 2) and (2, 1). But both of those require paths to (1, 1)—which we compute twice. As the grid grows, this redundancy explodes exponentially.
Notice how (1,1) appears in both branches of the recursion tree. The cells (0,1) and (1,0) are computed four times each! This exponential blowup is the hallmark of naive recursion on problems with overlapping subproblems—exactly the scenario where dynamic programming provides dramatic improvement.
The fix for overlapping subproblems is memoization: cache results of subproblems so we never recompute them. Since our state is defined by two indices (row, column), we need a 2D cache—either a 2D array or a dictionary with tuple keys.
Transformation Strategy:
This simple addition transforms exponential complexity to polynomial!
123456789101112131415161718192021222324252627282930313233
def unique_paths_memoization(m: int, n: int) -> int: """ Count unique paths using memoization (top-down DP). Time Complexity: O(m * n) - each cell computed exactly once Space Complexity: O(m * n) - memo table + O(m + n) recursion stack """ # Memoization cache: memo[row][col] = number of paths to (row, col) memo = {} def count_paths(row: int, col: int) -> int: # Base case: Out of bounds if row < 0 or col < 0: return 0 # Base case: Starting cell if row == 0 and col == 0: return 1 # Check memo before computing if (row, col) in memo: return memo[(row, col)] # Compute and store in memo result = count_paths(row - 1, col) + count_paths(row, col - 1) memo[(row, col)] = result return result return count_paths(m - 1, n - 1) # Now fast even for larger gridsprint(unique_paths_memoization(23, 12)) # Output: 193536720Complexity Analysis:
| Aspect | Before (Naive Recursion) | After (Memoization) |
|---|---|---|
| Time | O(2^(m+n)) | O(m × n) |
| Space | O(m + n) stack | O(m × n) memo + O(m+n) stack |
| 20×20 grid | ~137 billion calls | 400 calls |
| 100×100 grid | Infeasible | 10,000 calls (instant) |
The improvement is astronomical. Memoization eliminates all redundant computation by ensuring each (row, col) pair is computed exactly once.
Python provides @functools.lru_cache decorator that automatically memoizes function calls. For the unique paths problem: @lru_cache(maxsize=None) on count_paths eliminates manual memo management. However, understanding manual memoization is essential—lru_cache is syntactic sugar, not magic.
While memoization works, it still uses recursion—and recursion has overhead. For this problem, we can eliminate recursion entirely using tabulation: build a 2D table iteratively, filling cells in an order that respects dependencies.
The DP Table:
Create an m × n table where dp[i][j] represents the number of unique paths to reach cell (i, j) from (0, 0).
Filling Order:
Since each cell depends on the cell above and the cell to the left, we fill the table from top-left to bottom-right, row by row or column by column.
Recurrence Relation:
dp[i][j] = dp[i-1][j] + dp[i][j-1] (for i > 0 and j > 0)
dp[i][0] = 1 (only one way to reach any cell in first column: go down)
dp[0][j] = 1 (only one way to reach any cell in first row: go right)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
def unique_paths_tabulation(m: int, n: int) -> int: """ Count unique paths using tabulation (bottom-up DP). Time Complexity: O(m * n) - visit each cell once Space Complexity: O(m * n) - the DP table """ # Create m x n DP table initialized to 0 dp = [[0] * n for _ in range(m)] # Base case: First row - only one way (keep going right) for j in range(n): dp[0][j] = 1 # Base case: First column - only one way (keep going down) for i in range(m): dp[i][0] = 1 # Fill the rest of the table for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # Answer is in bottom-right corner return dp[m - 1][n - 1] # Example with step-by-step visualizationdef unique_paths_with_table_print(m: int, n: int) -> int: """Show the filled DP table for understanding.""" dp = [[0] * n for _ in range(m)] for j in range(n): dp[0][j] = 1 for i in range(m): dp[i][0] = 1 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # Print the table print("\nDP Table (number of paths to each cell):") for row in dp: print(" | ".join(f"{x:3}" for x in row)) return dp[m - 1][n - 1] print(f"\nAnswer: {unique_paths_with_table_print(3, 7)}")Visualizing the DP Table for a 3×7 Grid:
1 | 1 | 1 | 1 | 1 | 1 | 1
1 | 2 | 3 | 4 | 5 | 6 | 7
1 | 3 | 6 | 10 | 15 | 21 | 28
Reading the Table:
Notice the Pattern:
This is actually Pascal's Triangle rotated! The value at dp[i][j] equals C(i+j, i) = (i+j)!/(i! × j!). This combinatorial insight gives us an O(min(m,n)) mathematical solution, but the DP approach generalizes to problems where such closed-form solutions don't exist.
No recursion overhead, no risk of stack overflow, cache-friendly memory access patterns, and easier to reason about space optimization. For grid DP problems especially, bottom-up tabulation is typically the preferred approach in production code.
Examine the recurrence closely: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Each cell only depends on:
Key Insight:
We never need rows older than the previous row! This means we can reduce space from a full 2D table to just two rows (or even one row with careful implementation).
Rolling Array Technique:
Maintain only two arrays: prev_row and curr_row. After processing each row, the current row becomes the previous row for the next iteration.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
def unique_paths_two_rows(m: int, n: int) -> int: """ Space-optimized version using two rows. Time Complexity: O(m * n) Space Complexity: O(n) - only two rows of length n """ # Initialize previous row (all 1s for first row logic) prev_row = [1] * n for i in range(1, m): # Current row starts with 1 (first column always 1) curr_row = [1] * n for j in range(1, n): # dp[i][j] = dp[i-1][j] + dp[i][j-1] # prev_row[j] is dp[i-1][j] (cell above) # curr_row[j-1] is dp[i][j-1] (cell to left) curr_row[j] = prev_row[j] + curr_row[j - 1] # Current becomes previous for next iteration prev_row = curr_row return prev_row[n - 1] def unique_paths_one_row(m: int, n: int) -> int: """ Ultimate space optimization: single row, in-place updates. Time Complexity: O(m * n) Space Complexity: O(n) - single row (or O(min(m,n)) if we optimize further) """ # Single row, all 1s initially dp = [1] * n for i in range(1, m): for j in range(1, n): # Before update: dp[j] contains value from previous row (above) # dp[j-1] already updated in this iteration (left) dp[j] = dp[j] + dp[j - 1] return dp[n - 1] # Verification: All three approaches give same answerprint(unique_paths_two_rows(10, 15)) # Output: 817190print(unique_paths_one_row(10, 15)) # Output: 817190Understanding the Single-Row Magic:
The single-row optimization works because of processing order:
dp[j], dp[j-1] has already been updated (current row's left neighbor)dp[j] still holds the old value (previous row's same position)dp[j] + dp[j-1] correctly sums "above" and "left"This is a fundamental pattern in 2D DP space optimization. Whenever dependencies are limited to adjacent rows/columns, we can often reduce O(m×n) space to O(n) or O(m).
| Approach | Space Complexity | Additional Notes |
|---|---|---|
| Full 2D Table | O(m × n) | Easiest to understand, can trace any cell |
| Two Rows | O(n) | Clear separation of current/previous |
| Single Row | O(n) | Most compact, requires careful update order |
| Single Row + Swap | O(min(m, n)) | Choose smaller dimension for row |
Real-world grids often have obstacles. The variation Unique Paths II adds this constraint: some cells are blocked, and the robot cannot pass through them.
Problem Modification:
Given an m × n grid where:
obstacleGrid[i][j] = 0 means the cell is emptyobstacleGrid[i][j] = 1 means the cell is blockedCount unique paths from top-left to bottom-right, avoiding obstacles.
DP Modification:
if obstacle[i][j] == 1:
dp[i][j] = 0 // Can't reach a blocked cell
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1] // Normal case
The key insight: if a cell is blocked, there are zero ways to reach it, which propagates correctly through the DP.
1234567891011121314151617181920212223242526272829303132333435363738394041
def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int: """ Count unique paths avoiding obstacles. Args: obstacle_grid: 2D grid where 1 = blocked, 0 = empty Time Complexity: O(m * n) Space Complexity: O(n) with space optimization """ m = len(obstacle_grid) n = len(obstacle_grid[0]) # Edge case: start or end is blocked if obstacle_grid[0][0] == 1 or obstacle_grid[m-1][n-1] == 1: return 0 # Space-optimized single row dp = [0] * n dp[0] = 1 # Starting cell for i in range(m): for j in range(n): # If current cell is obstacle, zero paths through it if obstacle_grid[i][j] == 1: dp[j] = 0 elif j > 0: # Add paths from left (dp[j] already has paths from above) dp[j] += dp[j - 1] # If j == 0 and no obstacle, dp[j] keeps its value from above return dp[n - 1] # Examplegrid = [ [0, 0, 0], [0, 1, 0], # Obstacle in the middle [0, 0, 0]]print(unique_paths_with_obstacles(grid)) # Output: 2Understanding Obstacle Propagation:
Grid: DP Table:
0 0 0 1 1 1
0 1 0 → 1 0 1
0 0 0 1 1 2
The obstacle at (1,1) creates a "shadow"—cells that can only be reached from one direction instead of two. The blocked cell has 0 paths, which propagates correctly.
Edge Cases to Handle:
Notice how elegant the solution is: we don't need special logic for "paths blocked by obstacle." Setting dp[i][j] = 0 for obstacles automatically handles all downstream effects through the normal DP recurrence. This is a hallmark of well-designed DP: the recurrence naturally handles edge cases.
The unique paths problem is the simplest member of a large family of grid DP problems. The same core technique—2D table, recurrence based on neighbors—applies with modifications:
Minimum Path Sum:
Instead of counting paths, find the path with minimum sum of cell values.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Maximum Path Sum:
Same structure, but use max instead of min.
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])Dungeon Game:
Find minimum starting health to survive a grid with positive (healing) and negative (damage) cells.
Triangle:
Find minimum path sum in a triangular grid where you can only move to adjacent cells in the next row.
dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])All these problems share the 2D grid structure where each cell's value depends on specific neighbors. Master the unique paths problem thoroughly, and you'll find the others are natural extensions—same structure, different recurrence.
For the basic unique paths problem (no obstacles), there's an elegant O(min(m,n)) mathematical solution based on combinatorics.
The Insight:
To go from (0,0) to (m-1, n-1), the robot must make exactly:
m - 1 moves down (D)n - 1 moves right (R)Any valid path is just an arrangement of these moves. For example, in a 3×7 grid: RRRRRRDD, RRDRRRD, etc.
Counting Arrangements:
We need to choose which (m-1) positions out of (m+n-2) total positions are "down" moves. This is:
C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)
For a 3×7 grid: C(8, 2) = 8!/(2! × 6!) = 28 ✓
1234567891011121314151617181920212223242526272829303132333435
from math import comb # Python 3.8+ def unique_paths_combinatorial(m: int, n: int) -> int: """ O(min(m, n)) solution using combinatorics. The number of paths equals C(m+n-2, m-1) = C(m+n-2, n-1) (Choose which moves are "down" from total moves) """ return comb(m + n - 2, m - 1) # Manual implementation without math.combdef unique_paths_combinatorial_manual(m: int, n: int) -> int: """ Compute C(m+n-2, min(m-1, n-1)) efficiently. Time Complexity: O(min(m, n)) Space Complexity: O(1) """ # Choose smaller value for fewer multiplications numerator_terms = m + n - 2 choose_k = min(m - 1, n - 1) result = 1 for i in range(choose_k): # Compute C(n, k) = n*(n-1)*...*(n-k+1) / k! # Multiply then divide to keep intermediate values reasonable result = result * (numerator_terms - i) // (i + 1) return result print(unique_paths_combinatorial(3, 7)) # 28print(unique_paths_combinatorial_manual(3, 7)) # 28print(unique_paths_combinatorial(100, 100)) # Huge number, instantWhen to Use Which Approach:
| Approach | Time | Space | Use When |
|---|---|---|---|
| DP (tabulation) | O(m×n) | O(n) | Obstacles, custom weights, variants |
| Combinatorial | O(min(m,n)) | O(1) | Basic counting, large grids |
The combinatorial solution is faster and uses constant space, but it only works for the basic problem. The moment you add obstacles, weights, or other constraints, you need the DP approach.
This is a general lesson: DP is versatile but not always optimal. For specific problems, mathematical insights can yield better algorithms. But DP works when those insights don't exist.
In interviews, start with the DP solution—it demonstrates algorithmic thinking. Then mention the combinatorial optimization as an insight. This shows both practical problem-solving and mathematical awareness. If obstacles are mentioned, explain why DP becomes necessary.
The unique paths problem serves as the perfect introduction to 2D dynamic programming. Let's consolidate what we've learned:
dp[i][j] = dp[i-1][j] + dp[i][j-1] encodes the insight that paths to (i,j) come from above or left.dp[i][j] = 0 for blocked cells; propagation handles all downstream effects.C(m+n-2, m-1), but DP generalizes to variants.The Mental Model:
Think of the DP table as an accumulator of possibilities. Each cell collects all the ways to reach it from legal predecessor cells. The answer accumulates at the destination.
What's Next:
With grid paths mastered, we're ready for the crown jewel of 2D DP: the Longest Common Subsequence problem. It applies the same 2D table structure but to sequence comparison—opening doors to string algorithms, bioinformatics, and diff utilities.
You now understand the fundamental 2D DP problem: Unique Paths in Grid. This understanding forms the foundation for all grid-based DP and extends to any problem where state requires two indices. Next, we'll apply these same principles to the powerful Longest Common Subsequence problem.