Unique Paths in Grid DP in DSA Typescript - Execution Trace

Concept Flow - Unique Paths in Grid DP

Start at top-left cell

↓

Initialize DP table with 1s in first row and column

↓

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

↓

Calculate dp[i

↓

Repeat until bottom-right cell

↓

Return dp[m-1

We fill a grid table where each cell counts paths from start by adding paths from top and left cells, starting with 1s on the first row and column.

Execution Sample

DSA Typescript

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({length: m}, (_, i) => Array.from({length: n}, (_, j) => (i === 0 || j === 0) ? 1 : 0));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }
  return dp[m-1][n-1];
}

This code calculates the number of unique paths in an m x n grid moving only right or down.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State	Explanation
0	Initialize DP table	All cells	1 in first row and column, 0 elsewhere	[[1,1,1],[1,0,0],[1,0,0]]	First row and column set to 1 because only one way to reach those cells
1	Calculate dp[1][1]	(1,1)	dp[0][1] + dp[1][0] = 1 + 1 = 2	[[1,1,1],[1,2,0],[1,0,0]]	Paths to (1,1) come from top and left cells
2	Calculate dp[1][2]	(1,2)	dp[0][2] + dp[1][1] = 1 + 2 = 3	[[1,1,1],[1,2,3],[1,0,0]]	Paths to (1,2) sum top and left paths
3	Calculate dp[2][1]	(2,1)	dp[1][1] + dp[2][0] = 2 + 1 = 3	[[1,1,1],[1,2,3],[1,3,0]]	Paths to (2,1) sum top and left paths
4	Calculate dp[2][2]	(2,2)	dp[1][2] + dp[2][1] = 3 + 3 = 6	[[1,1,1],[1,2,3],[1,3,6]]	Paths to bottom-right cell is total unique paths
5	Return result	dp[2][2]	6	[[1,1,1],[1,2,3],[1,3,6]]	Total unique paths in 3x3 grid is 6

💡 All cells computed, bottom-right cell dp[m-1][n-1] returned as result

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
dp	[[1,1,1],[1,0,0],[1,0,0]]	[[1,1,1],[1,2,0],[1,0,0]]	[[1,1,1],[1,2,3],[1,0,0]]	[[1,1,1],[1,2,3],[1,3,0]]	[[1,1,1],[1,2,3],[1,3,6]]	[[1,1,1],[1,2,3],[1,3,6]]

Key Moments - 3 Insights

Why do we set the first row and first column cells to 1 initially?

Because from the start cell, you can only move right along the first row or down along the first column, so there is exactly one way to reach each of those cells. This is shown in execution_table row 0.

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

Because to reach cell (i,j), you can only come from 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 1 to 4 in execution_table.

What does dp[m-1][n-1] represent at the end?

It represents the total number of unique paths from the top-left corner to the bottom-right corner of the grid, as shown in step 5 of execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the value computed for cell (2,1)?

A 4

B 2

C 3

D 6

💡 Hint

Check the 'Value Computed' column in execution_table row 3.

At which step does the dp table first show a value greater than 3?

A Step 4

B Step 2

C Step 3

D Step 1

💡 Hint

Look at the 'Value Computed' column and the DP Table State in execution_table rows.

If the grid size was 2x2 instead of 3x3, what would dp[1][1] be after computation?

A 1

B 2

C 3

D 4

💡 Hint

Recall dp[i][j] = dp[i-1][j] + dp[i][j-1], and first row and column are 1.

Concept Snapshot

Unique Paths in Grid DP:
- Use a 2D dp array of size m x n
- Initialize first row and column with 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 or down

Full Transcript

This concept shows how to find the number of unique paths in a grid from the top-left to bottom-right corner. We create a 2D table where each cell stores the count of ways to reach it. The first row and column are set to 1 because you can only move right or down along edges. For each other cell, the number of ways is the sum of ways from the cell above and the cell to the left. We fill the table row by row until we reach the bottom-right cell, which holds the total unique paths. The example uses a 3x3 grid and shows step-by-step how the dp table fills up, ending with 6 unique paths.