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 grid table where each cell counts paths from start by adding paths from top and left cells until reaching the end.

Execution Sample

DSA C++

int uniquePaths(int m, int n) {
  vector<vector<int>> dp(m, vector<int>(n, 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 an m x n grid moving only down or right.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State
0	Initialize DP table with 1s	All cells in first row and column	1	[[1,1,1],[1,1,1],[1,1,1]]
1	Calculate dp[1][1]	(1,1)	dp[0][1] + dp[1][0] = 1 + 1 = 2	[[1,1,1],[1,2,1],[1,1,1]]
2	Calculate dp[1][2]	(1,2)	dp[0][2] + dp[1][1] = 1 + 2 = 3	[[1,1,1],[1,2,3],[1,1,1]]
3	Calculate dp[2][1]	(2,1)	dp[1][1] + dp[2][0] = 2 + 1 = 3	[[1,1,1],[1,2,3],[1,3,1]]
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]]
5	Return result	(2,2)	6	[[1,1,1],[1,2,3],[1,3,6]]

💡 All cells computed, bottom-right cell dp[2][2] = 6 is returned as total unique paths

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
dp	[[1,1,1],[1,1,1],[1,1,1]]	[[1,1,1],[1,2,1],[1,1,1]]	[[1,1,1],[1,2,3],[1,1,1]]	[[1,1,1],[1,2,3],[1,3,1]]	[[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 initialize the first row and first column with 1s?

Because from the start cell, there is only one way to reach any cell in the first row (all moves right) or first column (all moves down). This is shown in step 0 of the execution_table.

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 are sum of paths to those two cells, as shown in steps 1 to 4.

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

It represents the total number of unique paths from the top-left to bottom-right cell, after filling the entire DP table, as shown in step 5.

Visual Quiz - 3 Questions

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

A 3

B 2

C 4

D 6

💡 Hint

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

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

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the DP Table State column and find when a value > 3 appears for the first time.

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

A 1

B 3

C 2

D 4

💡 Hint

Refer to the formula dp[i][j] = dp[i-1][j] + dp[i][j-1] and consider the smaller grid.

Concept Snapshot

Unique Paths DP:
- Create dp[m][n], fill first row & col with 1
- For each cell dp[i][j], dp[i][j] = dp[i-1][j] + dp[i][j-1]
- dp[m-1][n-1] holds total unique paths
- Moves allowed: right or down only
- Time: O(m*n), Space: O(m*n)

Full Transcript

This concept shows how to count unique paths in a grid using dynamic programming. We start by initializing a 2D table where the first row and first column are set to 1 because there is only one way to reach those cells by moving right or down only. Then, for each other cell, we calculate the number of ways to get there by adding the number of ways to the cell above and the cell to the left. This process continues until we fill the entire table. The value in the bottom-right cell is the total number of unique paths from the top-left to the bottom-right. The execution table traces each step of filling the table, showing the updated values and the state of the table after each calculation. Key moments clarify why initialization is done with 1s, why we add the two adjacent cells, and what the final dp value means. The visual quiz tests understanding of specific steps and values in the table. This method efficiently solves the problem with time and space complexity proportional to the grid size.

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?
Given a grid of size m x n, how many unique paths exist from the top-left corner to the bottom-right corner if you can only move right or down?

easy

A. The number of different ways to reach the bottom-right corner moving only right or down

B. The shortest path length from top-left to bottom-right

C. The maximum sum path from top-left to bottom-right

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible unique paths from the top-left to bottom-right corner of a grid, moving only right or down.

2. Step 2: Clarify what is being counted

   We count the number of ways to reach the destination, not the shortest path or sums.

3. Final Answer:

   The number of different ways to reach the bottom-right corner moving only right or down -> Option A

4. Quick Check:

   Unique paths count = number of ways [OK]

Hint: Count paths moving only right or down [OK]

Common Mistakes:

• Confusing path count with shortest path length
• Thinking about obstacles when none are given
• Mixing sum of values with path count

2. Which of the following is the correct way to initialize a 2D vector dp of size m x n with all values 0 in C++?

easy

A. std::vector dp(n, std::vector<int>(m));

B. std::vector<int> dp(m, n, 0);

C. std::vector dp(m, std::vector<int>(n, 0));

D. std::vector dp(m, std::vector<int>(n));

Solution

1. Step 1: Understand 2D vector initialization syntax

   In C++, a 2D vector is initialized by specifying rows and columns with default values.

2. Step 2: Check each option

   std::vector dp(m, std::vector<int>(n, 0)); correctly creates a vector with m rows and n columns, all initialized to 0.

3. Final Answer:

   std::vector dp(m, std::vector<int>(n, 0)); -> Option C

4. Quick Check:

   Correct 2D vector init syntax = std::vector dp(m, std::vector<int>(n, 0)); [OK]

Hint: Use vector of vectors with inner vector size and default value [OK]

Common Mistakes:

• Swapping m and n in initialization
• Using wrong vector constructor parameters
• Missing default value initialization

3. What is the output of the following C++ code snippet?

int m = 3, n = 3;
std::vector dp(m, std::vector<int>(n, 0));
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];
  }
}
std::cout << dp[m-1][n-1] << std::endl;

medium

A. 3

B. 9

C. 10

D. 6

Solution

1. Step 1: Initialize first row and column

   First row and column are set to 1, representing only one path to each cell along edges.

2. Step 2: Fill dp table using dp[i][j] = dp[i-1][j] + dp[i][j-1]

   Calculate dp values for inner cells:
   dp[1][1] = 1+1=2
   dp[1][2] = 1+2=3
   dp[2][1] = 2+1=3
   dp[2][2] = 3+3=6

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use DP formula dp[i][j] = dp[i-1][j] + dp[i][j-1] [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Using wrong indices in dp update
• Confusing addition with multiplication

4. Identify the error in the following code snippet for calculating unique paths in a grid:

int uniquePaths(int m, int n) {
  std::vector dp(m, std::vector<int>(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];
}

medium

A. The multiplication operator should be addition in dp update

B. The dp vector is not initialized with zeros

C. The loops should start from 0 instead of 1

D. The return statement should be dp[0][0]

Solution

1. Step 1: Check dp update formula

   The code uses multiplication: dp[i][j] = dp[i-1][j] * dp[i][j-1], which is incorrect for counting paths.

2. Step 2: Correct formula for unique paths

   The correct formula adds the number of ways from top and left cells: dp[i][j] = dp[i-1][j] + dp[i][j-1].

3. Final Answer:

   The multiplication operator should be addition in dp update -> Option A

4. Quick Check:

   Use addition, not multiplication for path counts [OK]

Hint: Sum paths from top and left cells, don't multiply [OK]

Common Mistakes:

• Using multiplication instead of addition in dp formula
• Returning wrong dp cell
• Not initializing first row or column

5. Given a grid with obstacles represented by 1s and empty spaces by 0s, how would you modify the unique paths DP solution to count paths avoiding obstacles?
Consider the grid:

0 0 0
0 1 0
0 0 0

hard

A. Set dp[i][j] = 1 for all cells regardless of obstacles

B. Set dp[i][j] = 0 if grid[i][j] is 1, else dp[i][j] = dp[i-1][j] + dp[i][j-1]

C. Multiply dp[i-1][j] and dp[i][j-1] if obstacle is present

D. Ignore obstacles and use normal dp formula

Solution

1. Step 1: Handle obstacles in dp initialization

   If a cell has an obstacle (value 1), set dp[i][j] = 0 because no path can go through it.

2. Step 2: Update dp values considering obstacles

   For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1], summing paths from top and left only if those cells are reachable.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] is 1, else dp[i][j] = dp[i-1][j] + dp[i][j-1] -> Option B

4. Quick Check:

   Obstacles block paths, set dp to 0 there [OK]

Hint: Zero dp for obstacles, sum paths otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Using multiplication instead of addition
• Setting dp to 1 for obstacle cells