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:
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 null null
null null null

Why: Only one way to reach any cell in the first row by moving right

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

1 -> 1 -> 1
1 null null
1 null null

Why: Only one way to reach any cell in the 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 null
1 null null

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 null null

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

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

1 -> 1 -> 1
1 -> 2 -> 3
1 -> 3 null

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

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

1 -> 1 -> 1
1 -> 2 -> 3
1 -> 3 -> 6

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

Result:

Final DP grid:
1 -> 1 -> 1
1 -> 2 -> 3
1 -> 3 -> 6
Answer: 6 unique paths

Annotated Code

DSA C#

using System;

class UniquePathsDP
{
    public static int UniquePaths(int m, int n)
    {
        int[,] dp = new int[m, n];

        // Initialize first row
        for (int col = 0; col < n; col++)
            dp[0, col] = 1; // Only one way to move right

        // Initialize first column
        for (int row = 0; row < m; row++)
            dp[row, 0] = 1; // Only one way to move down

        // Fill the rest of the grid
        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]; // sum paths from top and left
            }
        }

        return dp[m - 1, n - 1]; // bottom-right corner
    }

    static void Main()
    {
        int m = 3, n = 3;
        int result = UniquePaths(m, n);
        Console.WriteLine($"Number of unique paths in a {m}x{n} grid: {result}");
    }
}

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

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

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

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

dp[row, col] = dp[row - 1, col] + dp[row, col - 1];

Calculate paths for current cell by adding paths from top and left

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

Return total unique paths at 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 solutions without memoization which are exponential, this DP approach is efficient and avoids repeated calculations

Edge Cases

Grid with 1 row or 1 column

Returns 1 because only one path exists (all right or all down moves)

DSA C#

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

Grid size 1x1

Returns 1 because start and end are the same cell

DSA C#

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

When to Use This Pattern

When asked to count ways to move in a grid with restricted moves (right/down), use DP 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

Mistake: Adding dp[row, col - 1] and dp[row - 1, col] in wrong order or indices
Fix: Ensure dp[row, col] = dp[row - 1, col] + dp[row, col - 1] to sum top and left correctly

Summary

Calculates the number of unique paths from top-left to bottom-right in a grid moving only right or down.

Use when you need to count distinct routes in a grid with movement constraints.

The key insight is that paths to a cell equal the sum of paths to the cell above and to the left.

Practice

1. What does the problem "Unique Paths in Grid DP" typically ask you to find?

easy

A. The maximum sum path from the top-left to the bottom-right corner of a grid.

B. The shortest path length from the top-left to the bottom-right corner of a grid.

C. The number of different ways to move from the top-left to the bottom-right corner of a grid using only right and down moves.

D. The number of obstacles in the grid.

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Differentiate from other path problems

   It is not about shortest path or sums, but counting unique ways to reach the destination.

3. Final Answer:

   The number of different ways to move from the top-left to the bottom-right corner of a grid using only right and down moves. -> Option C

4. Quick Check:

   Unique paths count = number of ways [OK]

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

Common Mistakes:

• Confusing unique paths with shortest path length
• Including diagonal moves
• Counting obstacles instead of paths

2. Which of the following C# code snippets correctly initializes a 2D array for dynamic programming of size m x n?

easy

A. int[,] dp = new int[m, n];

B. int[][] dp = new int[m][n];

C. int[][] dp = new int[m, n];

D. int[,] dp = new int[m][];

Solution

1. Step 1: Recall C# 2D array syntax

   In C#, a rectangular 2D array is declared as int[,] dp = new int[m, n];

2. Step 2: Identify incorrect syntax

   Options B, C, and D misuse jagged array or rectangular array syntax.

3. Final Answer:

   int[,] dp = new int[m, n]; -> Option A

4. Quick Check:

   Rectangular 2D array uses [,] syntax [OK]

Hint: Use int[,] for 2D arrays, not jagged syntax [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Mixing rectangular and jagged array declarations
• Missing array size initialization

3. What is the output of the following C# code snippet for Unique Paths in a 3x3 grid?

int m = 3, n = 3;
int[,] dp = new int[m, 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];
    }
}
Console.WriteLine(dp[m - 1, n - 1]);

medium

A. 10

B. 3

C. 9

D. 6

Solution

1. Step 1: Initialize first row and column

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

2. Step 2: Calculate dp values for inner cells

   Each cell dp[i,j] = dp[i-1,j] + dp[i,j-1]. For 3x3 grid, dp[2,2] = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use dp[i,j] = dp[i-1,j] + dp[i,j-1] to fill grid [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding instead of summing paths
• Off-by-one errors in loops

4. Identify the error in the following C# code snippet for Unique Paths calculation:

int m = 3, n = 3;
int[,] dp = new int[m, 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];
    }
}
Console.WriteLine(dp[m - 1, n - 1]);

medium

A. The dp array is not initialized.

B. The loops use <= causing index out of range exception.

C. The dp formula is incorrect; it should subtract values.

D. The Console.WriteLine statement is missing a semicolon.

Solution

1. Step 1: Check loop boundaries

   Loops use i <= m and j <= n which exceed array bounds (max index m-1, n-1).

2. Step 2: Identify runtime error

   This causes IndexOutOfRangeException at runtime when accessing dp[m,0] or dp[0,n].

3. Final Answer:

   The loops use <= causing index out of range exception. -> Option B

4. Quick Check:

   Loop bounds must be less than array size [OK]

Hint: Use < not <= for array indices to avoid out of range [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring array index limits
• Misunderstanding zero-based indexing

5. Given a 4x5 grid with some obstacles represented by 1s, how would you modify the Unique Paths DP solution to count paths avoiding obstacles?

int[,] obstacleGrid = {
  {0,0,0,0,0},
  {0,1,0,1,0},
  {0,0,0,0,0},
  {1,0,1,0,0}
};

Which approach correctly adapts the DP solution?

hard

A. Initialize dp[i,j] = 0 if obstacleGrid[i,j] == 1; else dp[i,j] = dp[i-1,j] + dp[i,j-1] (with boundary checks). Initialize first row and column carefully considering obstacles.

B. Ignore obstacles and calculate dp as usual because obstacles don't affect path count.

C. Set dp[i,j] = 1 for all cells and subtract 1 for obstacles at the end.

D. Use recursion without memoization to handle obstacles.

Solution

1. Step 1: Set dp to 0 where obstacles exist

   For cells with obstacleGrid[i,j] == 1, dp[i,j] must be 0 to block paths.

2. Step 2: Calculate dp with obstacle checks

   For other cells, dp[i,j] = dp[i-1,j] + dp[i,j-1], ensuring no paths through obstacles. Initialize first row and column carefully to stop paths after obstacles.

3. Final Answer:

   Initialize dp[i,j] = 0 if obstacleGrid[i,j] == 1; else dp[i,j] = dp[i-1,j] + dp[i,j-1] (with boundary checks). Initialize first row and column carefully considering obstacles. -> Option A

4. Quick Check:

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

Hint: Set dp=0 on obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Not initializing first row/column correctly with obstacles
• Using recursion without memoization causing inefficiency