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

Recall & Review

beginner

What is the problem statement of 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 Unique Paths problem?

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

intermediate

What is the recurrence relation for Unique Paths DP?

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

beginner

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

Because there is only one way to reach any cell in the first row (all right moves) or first column (all down moves).

advanced

How does the Unique Paths DP solution relate to Pascal's Triangle?

The number of unique paths corresponds to combinations, similar to values in Pascal's Triangle, as each cell sums paths from two directions.

In Unique Paths DP, what does dp[0][0] represent?

A Number of obstacles

B Number of ways to reach bottom-right

C Starting point with 1 path

D Number of rows

dp[0][0] is the start cell, so it has exactly 1 way to be at.

Which moves are allowed in the Unique Paths grid problem?

A Up and Left

B Down and Right

C Up and Right

D Down and Left

Only moves down or right are allowed to reach the destination.

What is the time complexity of the DP solution for Unique Paths in an m x n grid?

A O(m * n)

B O(m + n)

C O(m^2 * n^2)

D O(1)

We fill each cell once, so time is proportional to m times n.

If dp[i][j] = dp[i-1][j] + dp[i][j-1], what does dp[i-1][j] represent?

A Paths from top cell

B Paths from bottom cell

C Paths from left cell

D Paths from right cell

dp[i-1][j] is the number of ways to reach the cell above (top).

How do obstacles affect the Unique Paths DP solution?

A They double the paths

B They add one extra path

C They have no effect

D They block paths, so dp value is 0 for that cell

Obstacles block paths, so dp for those cells is zero.

Explain how to build the DP table for Unique Paths in a grid.

Think about how you can only move right or down.

Describe the difference between Unique Paths with and without obstacles in DP.

Consider how obstacles block movement.

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