Unique Paths in Grid DP in DSA C++

Mental Model

Count how many ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south. You want to know how many different routes you can take to reach your friend's house at the bottom-right corner.

Start (S) at top-left, End (E) at bottom-right in a 3x3 grid:
S -> [] -> []
↓    ↓    ↓
[] -> [] -> []
↓    ↓    ↓
[] -> [] -> E

Dry Run Walkthrough

Input: grid size: 3 rows x 3 columns

Goal: Find the number of unique paths from top-left to bottom-right moving only right or down

Step 1: Initialize first row with 1s because only one way to move right

[1] -> [1] -> [1]
null

Why: Only one way to reach cells in first row by moving right

Step 2: Initialize first column with 1s because only one way to move down

[1]
↓
[1]
↓
[1]

Why: Only one way to reach cells in first column by moving down

Step 3: Calculate paths for cell (1,1) by adding paths from top (0,1) and left (1,0)

[1] -> [1] -> [1]
↓      ↓      ↓
[1] -> [2] -> []
↓      ↓      ↓
[1] -> [] -> []

Why: Paths to (1,1) = paths from above + paths from left

Step 4: Calculate paths for cell (1,2) similarly

[1] -> [1] -> [1]
↓      ↓      ↓
[1] -> [2] -> [3]
↓      ↓      ↓
[1] -> [] -> []

Why: Sum paths from top and left for each cell

Step 5: Calculate paths for cell (2,1)

[1] -> [1] -> [1]
↓      ↓      ↓
[1] -> [2] -> [3]
↓      ↓      ↓
[1] -> [3] -> []

Why: Continue filling grid by summing top and left paths

Step 6: Calculate paths for cell (2,2) - bottom-right corner

[1] -> [1] -> [1]
↓      ↓      ↓
[1] -> [2] -> [3]
↓      ↓      ↓
[1] -> [3] -> [6]

Why: Final cell paths = sum of top and left paths, total unique paths

Result:

Final grid with path counts:
[1] -> [1] -> [1]
↓      ↓      ↓
[1] -> [2] -> [3]
↓      ↓      ↓
[1] -> [3] -> [6]
Answer: 6 unique paths

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class UniquePaths {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // Initialize first row
        for (int col = 0; col < n; ++col) {
            dp[0][col] = 1;
        }
        // Initialize first column
        for (int row = 0; row < m; ++row) {
            dp[row][0] = 1;
        }
        // Fill dp table
        for (int row = 1; row < m; ++row) {
            for (int col = 1; col < n; ++col) {
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

int main() {
    UniquePaths solver;
    int m = 3, n = 3;
    int result = solver.uniquePaths(m, n);
    cout << "Number of unique paths in a " << m << "x" << n << " grid: " << result << endl;
    return 0;
}

for (int col = 0; col < n; ++col) { dp[0][col] = 1; }

Initialize first row with 1s because only one way to move right

for (int row = 0; row < m; ++row) { dp[row][0] = 1; }

Initialize first column with 1s because only one way to move down

for (int row = 1; row < m; ++row) { for (int col = 1; col < n; ++col) { dp[row][col] = dp[row - 1][col] + dp[row][col - 1]; } }

Fill each cell by summing paths from top and left neighbors

return dp[m - 1][n - 1];

Return total unique paths to bottom-right corner

Output

Number of unique paths in a 3x3 grid: 6

Complexity Analysis

Time: O(m*n) because we fill each cell in the grid once

Space: O(m*n) because we store path counts for each cell in a 2D array

vs Alternative: Compared to recursive approach without memoization which is exponential, this DP approach is efficient and avoids repeated calculations

Edge Cases

1x1 grid

Only one cell means only one path (start is end)

DSA C++

return dp[m - 1][n - 1];

1xn or mx1 grid

Only one path because movement is restricted to one direction

DSA C++

for (int col = 0; col < n; ++col) { dp[0][col] = 1; } and for (int row = 0; row < m; ++row) { dp[row][0] = 1; }

When to Use This Pattern

When you see a grid and need to count ways to reach a point moving only right or down, use dynamic programming to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing the first row and first column with 1s
Fix: Explicitly set dp[0][col] and dp[row][0] to 1 before filling the rest of the grid

Mistake: Using recursion without memoization causing timeouts
Fix: Use bottom-up DP with a 2D array to store intermediate results

Summary

Calculates the number of unique paths in a grid moving only right or down.

Use when counting distinct routes in a grid with movement constraints.

Each cell's paths count is the sum of paths from the cell above and the cell to the left.

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