Unique Paths in Grid DP in DSA C# - Execution Trace

Concept Flow - Unique Paths in Grid DP

Start at top-left cell

↓

Initialize DP table with 1s in first row and column

↓

For each cell (i,j) from (1,1) to (m-1,n-1)

↓

Calculate dp[i

↓

Fill DP table row by row

↓

Result is dp[m-1

↓

End

We fill a table where each cell counts paths from start by adding paths from top and left cells, ending at bottom-right.

Execution Sample

DSA C#

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

This code counts unique paths in a grid by building a DP table where each cell sums paths from above and left.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State
1	Initialize first column	(0,0)	1	[[1,0,0],[0,0,0],[0,0,0]]
2	Initialize first column	(1,0)	1	[[1,0,0],[1,0,0],[0,0,0]]
3	Initialize first column	(2,0)	1	[[1,0,0],[1,0,0],[1,0,0]]
4	Initialize first row	(0,1)	1	[[1,1,0],[1,0,0],[1,0,0]]
5	Initialize first row	(0,2)	1	[[1,1,1],[1,0,0],[1,0,0]]
6	Calculate dp[1,1]	(1,1)	dp[0,1]+dp[1,0]=1+1=2	[[1,1,1],[1,2,0],[1,0,0]]
7	Calculate dp[1,2]	(1,2)	dp[0,2]+dp[1,1]=1+2=3	[[1,1,1],[1,2,3],[1,0,0]]
8	Calculate dp[2,1]	(2,1)	dp[1,1]+dp[2,0]=2+1=3	[[1,1,1],[1,2,3],[1,3,0]]
9	Calculate dp[2,2]	(2,2)	dp[1,2]+dp[2,1]=3+3=6	[[1,1,1],[1,2,3],[1,3,6]]
10	Return result	dp[2,2]	6	[[1,1,1],[1,2,3],[1,3,6]]

💡 All cells filled; dp[m-1,n-1] = 6 is the total unique paths.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 6	After Step 9	Final
dp	[[0,0,0],[0,0,0],[0,0,0]]	[[1,0,0],[0,0,0],[0,0,0]]	[[1,1,1],[1,0,0],[1,0,0]]	[[1,1,1],[1,2,3],[1,0,0]]	[[1,1,1],[1,2,3],[1,3,6]]	[[1,1,1],[1,2,3],[1,3,6]]
m	3	3	3	3	3	3
n	3	3	3	3	3	3

Key Moments - 3 Insights

Why do we set the first row and first column cells to 1 before filling the rest?

Because from the start cell, there is only one way to reach any cell in the first row (all moves right) or first column (all moves down). This is shown in execution_table rows 1-5 where these cells are set to 1.

Why do we add dp[i-1,j] and dp[i,j-1] to get dp[i,j]?

Because any cell can be reached either from the cell above it or from the cell to its left. So total paths to dp[i,j] is sum of paths to those two cells, as shown in execution_table rows 6-9.

What does dp[m-1,n-1] represent at the end?

It represents the total number of unique paths from the top-left to bottom-right cell, after filling the entire DP table, as shown in execution_table row 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value computed for dp[1,1]?

A 2

B 1

C 3

D 4

💡 Hint

Check the 'Value Computed' column in execution_table row 6.

At which step does the condition to stop filling the DP table occur?

A Step 5

B Step 9

C Step 10

D Step 1

💡 Hint

Look at the 'exit_note' and the last step in execution_table.

If the grid size was 2x2 instead of 3x3, what would be the final dp[m-1,n-1] value?

A 3

B 2

C 4

D 1

💡 Hint

Think about the smaller DP table initialization and filling logic shown in variable_tracker.

Concept Snapshot

Unique Paths DP:
- Use a 2D dp array of size m x n
- Initialize first row and column to 1
- For each cell dp[i][j], dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Result is dp[m-1][n-1]
- Counts unique paths moving only right or down

Full Transcript

This concept shows how to count unique paths in a grid using dynamic programming. We create a 2D table dp where each cell stores the number of ways to reach it from the start. First, we set the first row and first column cells to 1 because there is only one way to reach those cells by moving only right or down. Then, for each other cell, we add the number of paths from the cell above and the cell to the left. We fill the table row by row until we reach the bottom-right cell. The value in dp[m-1,n-1] is the total number of unique paths. The execution table traces each step of filling the dp table for a 3x3 grid, showing how values are computed and updated. The variable tracker shows the dp table state after key steps. Key moments clarify why initialization is needed and how the dp formula works. The visual quiz tests understanding of dp values and stopping condition. This method efficiently solves the unique paths problem by building on smaller subproblems.

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