Unique Paths in Grid DP in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the problem statement of the Unique Paths in Grid DP?

Find the number of unique ways to move from the top-left corner to the bottom-right corner of a grid, moving only down or right.

beginner

What does the DP state represent in the Unique Paths problem?

DP state dp[i][j] represents the number of unique paths to reach cell (i, j) from the start.

beginner

What is the base case for the Unique Paths DP solution?

The first row and first column cells have only 1 unique path each because you can only move right or down respectively.

intermediate

Write the recurrence relation for dp[i][j] in Unique Paths.

dp[i][j] = dp[i-1][j] + dp[i][j-1], summing paths from the top and left cells.

intermediate

Why is Dynamic Programming suitable for the Unique Paths problem?

Because the problem has overlapping subproblems and optimal substructure, allowing reuse of computed results to avoid repeated work.

In the Unique Paths problem, which moves are allowed?

A Only left and up

B Only diagonal moves

C Right, down, left, and up

D Only right and down

The problem restricts moves to only right and down directions.

What is the value of dp[0][0] in the Unique Paths DP table?

A 0

B 1

C Number of rows

D Number of columns

Starting cell has exactly one way to be at itself.

If the grid size is 3x3, how many unique paths are there from top-left to bottom-right?

A 6

B 12

C 9

D 3

For a 3x3 grid, the number of unique paths is 6.

Which of these best describes the time complexity of the DP solution for Unique Paths?

A O(m+n)

B O(2^(m+n))

C O(m*n)

D O(1)

The DP table has m rows and n columns, so time complexity is O(m*n).

What does dp[i][j] depend on in the Unique Paths DP solution?

A dp[i-1][j] and dp[i][j-1]

B dp[i][j-1] only

C dp[i-1][j] only

D dp[i+1][j] and dp[i][j+1]

dp[i][j] is the sum of paths from the top cell and left cell.

Explain how to build the DP table for the Unique Paths problem step-by-step.

Think about how you can reach each cell from its neighbors.

Describe why the Unique Paths problem can be solved efficiently using Dynamic Programming instead of recursion alone.

Consider what happens if you calculate paths for the same cell multiple times.

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