Visualization of Unique Paths (DFS and DP)

The Unique Paths problem asks: given a grid of size m×n, how many unique paths exist from the top-left corner to the bottom-right corner? You can only move right or down at each step. This visualization demonstrates two different approaches to solving this problem - first using a brute force DFS approach, and then showing how Dynamic Programming can optimize the solution by reusing calculations.

DFS Visualization of Unique Paths

DFS Path Finding

View Problem
Start Cell (0,0)
Target Cell
Current Cell
Current Path
Rows
3
Columns
3
Speed
1
0
STEP1
Current Position:(0, 0)
Exploring path...
CURRENT PATH
(0, 0)
PATHS FOUND
0

DFS Implementation

1def uniquePaths(self, m: int, n: int) -> int:
2 cnt = 0
3
4 def dfs(row, col):
5 nonlocal cnt
6
7 if row >= m or col >= n:
8 return
9
10 if row == m - 1 and col == n - 1:
11 cnt += 1
12 return
13
14 dfs(row, col + 1)
15 dfs(row + 1, col)
16
17 dfs(0, 0)
18 return cnt

From DFS to Dynamic Programming: Understanding the Need for Optimization

Looking at the DFS visualization above, you might notice something inefficient. As the DFS explores each possible path, it repeatedly calculates the same subproblems. For example, when it reaches position (1,1), it calculates all possible paths from that point to the target - but it will do this calculation multiple times, once for each different way of reaching (1,1)!

This is where Dynamic Programming shines. Instead of recalculating paths from each position multiple times, we can calculate it once and reuse that result. Watch the DP visualization below and notice how:

  • Each cell only needs to be calculated once
  • The value in each cell represents the total number of possible paths from the start to that cell
  • To calculate a cell's value, we just add the values from the cells above and to the left (our previous calculations)

This "building upon previous calculations" is the essence of Dynamic Programming. It transforms our solution from repeatedly solving the same subproblems to solving each subproblem exactly once and reusing those results.

Dynamic Programming Visualization

Unique Paths DP Visualizer

Link to the problem
Start Cell
End Cell
Current Cell
Checking Neighbors
Processed Cell
Unprocessed Cell
Rows
3
Columns
3
Speed
1

Python Implementation

1def unique_paths(n: int, m: int) -> int:
2 # Initialize dp table with zeros and set base case
3 dp = [[0] * m for _ in range(n)]
4 dp[0][0] = 1
5
6 # Fill dp table bottom-up
7 for i in range(n):
8 for j in range(m):
9 # Skip starting position
10 if i == 0 and j == 0:
11 continue
12
13 # Get paths from up and left
14 up = dp[i-1][j] if i > 0 else 0
15 left = dp[i][j-1] if j > 0 else 0
16 dp[i][j] = up + left
17
18 return dp[n-1][m-1]