Unique Paths in Grid DP in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unique Paths Calculation

What is the output of the following C++ code that calculates unique paths in a 3x3 grid?

DSA C++

int uniquePaths(int m, int n) {
    int dp[3][3] = {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];
        }
    }
    return dp[m-1][n-1];
}

int main() {
    int result = uniquePaths(3, 3);
    std::cout << result << std::endl;
    return 0;
}

A 5

B 3

C 6

D 9

💡 Hint

Think about how many ways you can move right or down to reach the bottom-right corner in a 3x3 grid.

The number of unique paths in a 3x3 grid moving only right or down is 6. The dp table counts all ways to reach each cell by summing ways from the top and left cells.

🧠 Conceptual

intermediate

Understanding DP Table Initialization

Why do we initialize the first row and first column of the DP table with 1 in the Unique Paths problem?

A Because the first row and column are not used in the calculation.

B Because the first row and column represent obstacles that block paths.

C Because the first row and column are always zero in the problem.

D Because there is only one way to reach any cell in the first row or first column, by moving only right or only down respectively.

💡 Hint

Think about how you can move from the start to cells in the first row or column.

The first row cells can only be reached by moving right from the start, so only one path exists. Similarly, the first column cells can only be reached by moving down, so only one path exists.

❓ Predict Output

advanced

Output with Obstacle Grid

What is the output of the following C++ code that calculates unique paths in a 3x3 grid with an obstacle at position (1,1)?

DSA C++

int uniquePathsWithObstacles(int obstacleGrid[3][3]) {
    int dp[3][3] = {0};
    if (obstacleGrid[0][0] == 1) return 0;
    dp[0][0] = 1;
    for (int i = 1; i < 3; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
    }
    for (int j = 1; j < 3; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
    }
    for (int i = 1; i < 3; i++) {
        for (int j = 1; j < 3; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[2][2];
}

int main() {
    int grid[3][3] = {{0,0,0},{0,1,0},{0,0,0}};
    int result = uniquePathsWithObstacles(grid);
    std::cout << result << std::endl;
    return 0;
}

A 2

B 4

C 3

D 0

💡 Hint

The obstacle blocks some paths, reducing the total number of unique paths.

The obstacle at (1,1) blocks paths passing through that cell. The dp table counts only paths avoiding the obstacle. The total unique paths to bottom-right is 2.

🔧 Debug

advanced

Identify the Bug in DP Implementation

The following code is intended to calculate unique paths in an m x n grid but produces incorrect results. What is the bug?

DSA C++

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

A The code uses multiplication instead of addition when filling dp[i][j].

B The function returns dp[0][0] instead of dp[m-1][n-1].

C The loops start from 1 instead of 0 causing out-of-bound errors.

D The dp array is not initialized for the first row and column.

💡 Hint

Think about how the number of paths to a cell is calculated from its neighbors.

The number of unique paths to a cell is the sum of paths from the cell above and the cell to the left, not the product.

🚀 Application

expert

Number of Unique Paths in a Large Grid

You want to find the number of unique paths in a 20x20 grid moving only right or down. Which approach is best to compute this efficiently?

A Use a dynamic programming table of size 20x20 to compute paths iteratively.

B Calculate the binomial coefficient C(38,19) using a direct formula or efficient method.

C Use recursion without memoization to explore all paths.

D Use a depth-first search to count all paths.

💡 Hint

Think about combinatorics and how many moves are needed to reach the bottom-right corner.

The number of unique paths in an m x n grid is the binomial coefficient C(m+n-2, m-1). For large grids, computing this directly is more efficient than DP or recursion.

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