Unique Paths in Grid DP in DSA C - Execution Trace

Concept Flow - Unique Paths in Grid DP

Start at top-left cell (0,0)

↓

Initialize DP table with 1s in first row and first column

↓

For each cell (i,j) from (1,1) to (m-1,n-1)

↓

Calculate dp[i

↓

Repeat until bottom-right cell (m-1,n-1)

↓

Return dp[m-1

We fill a table where each cell counts paths from start by adding paths from top and left cells, building up to the bottom-right.

Execution Sample

DSA C

int uniquePaths(int m, int n) {
  int dp[m][n];
  for (int i = 0; i < m; i++) dp[i][0] = 1;
  for (int j = 0; j < n; j++) dp[0][j] = 1;
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }
  return dp[m-1][n-1];
}

This code counts unique paths in a grid by dynamic programming, summing paths from above and left cells.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State
1	Initialize first column	(0,0)	1	[[1, _, _], [_, _, _], [_, _, _]]
2	Initialize first column	(1,0)	1	[[1, _, _], [1, _, _], [_, _, _]]
3	Initialize first column	(2,0)	1	[[1, _, _], [1, _, _], [1, _, _]]
4	Initialize first row	(0,0)	1	[[1, _, _], [1, _, _], [1, _, _]]
5	Initialize first row	(0,1)	1	[[1, 1, _], [1, _, _], [1, _, _]]
6	Initialize first row	(0,2)	1	[[1, 1, 1], [1, _, _], [1, _, _]]
7	Compute dp[1][1]	(1,1)	dp[0][1] + dp[1][0] = 1 + 1 = 2	[[1, 1, 1], [1, 2, _], [1, _, _]]
8	Compute dp[1][2]	(1,2)	dp[0][2] + dp[1][1] = 1 + 2 = 3	[[1, 1, 1], [1, 2, 3], [1, _, _]]
9	Compute dp[2][1]	(2,1)	dp[1][1] + dp[2][0] = 2 + 1 = 3	[[1, 1, 1], [1, 2, 3], [1, 3, _]]
10	Compute dp[2][2]	(2,2)	dp[1][2] + dp[2][1] = 3 + 3 = 6	[[1, 1, 1], [1, 2, 3], [1, 3, 6]]
11	Return result	dp[2][2]	6	[[1, 1, 1], [1, 2, 3], [1, 3, 6]]

💡 All cells computed, bottom-right cell dp[2][2] holds total unique paths.

Variable Tracker

Variable	Start	After Step 7	After Step 8	After Step 9	After Step 10	Final
dp[0][0]	undefined	1	1	1	1	1
dp[1][1]	undefined	2	2	2	2	2
dp[1][2]	undefined	undefined	3	3	3	3
dp[2][1]	undefined	undefined	undefined	3	3	3
dp[2][2]	undefined	undefined	undefined	undefined	6	6

Key Moments - 3 Insights

Why do we set the first row and first column cells to 1 before filling the rest?

Because from the start cell, you can only move right along the first row or down along the first column, so there is exactly 1 unique path to each of these cells. This is shown in steps 1-6 in the execution_table.

Why do we add dp[i-1][j] and dp[i][j-1] to get dp[i][j]?

Because any path to cell (i,j) must come from either the cell above (i-1,j) or the cell to the left (i,j-1). So total paths to (i,j) is sum of paths to those two cells, as shown in steps 7-10.

Why does the loop start from i=1 and j=1 instead of 0?

Because the first row and first column are already initialized with 1s, so we start filling from the second row and column to avoid overwriting those base cases, as seen in the code and execution_table steps.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the value computed for dp[2][2]?

A 6

B 5

C 3

D 4

💡 Hint

Check the 'Value Computed' column at step 10 in execution_table.

At which step does the condition to compute dp[1][2] happen?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for the row where 'Cell Updated' is (1,2) in execution_table.

If we did not initialize the first row with 1s, what would happen to dp[0][2]?

A It would be 2 because of addition

B It would be 1 anyway from dp[0][1]

C It would remain 0 or undefined, causing wrong path counts

D It would cause a runtime error

💡 Hint

Refer to variable_tracker and initialization steps 4-6 in execution_table.

Concept Snapshot

Unique Paths DP:
- Use a 2D dp array of size m x n
- Initialize first row and column to 1
- For each cell dp[i][j], dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Result is dp[m-1][n-1]
- Counts unique ways moving only right/down

Full Transcript

This visualization traces the dynamic programming solution for counting unique paths in a grid. We start by initializing the first row and first column cells to 1, because from the start cell, you can only move right or down along these edges, so there is exactly one path to each. Then, for each other cell, we compute the number of unique paths by adding the paths from the cell above and the cell to the left. This builds up the dp table step-by-step until we reach the bottom-right cell, which holds the total number of unique paths. The execution table shows each step updating the dp table, and the variable tracker follows key dp cells' values. Common confusions include why the first row and column are initialized to 1, why we add the two neighboring cells, and why loops start from 1. The quiz questions test understanding of these steps and values.