Unique Paths in Grid DP in DSA C# - Deep Dive

Overview - Unique Paths in Grid DP

What is it?

Unique Paths in Grid DP is a way to count how many different ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down. It uses a table to remember results of smaller steps to avoid repeating work. This method helps solve problems where you want to find the number of possible routes in a grid-like path. It is a classic example of dynamic programming, which breaks big problems into smaller, easier ones.

Why it matters

Without this method, counting all possible paths would take a very long time because you would try every route one by one. This would be slow and inefficient, especially for big grids. Using dynamic programming to find unique paths saves time and makes it possible to solve problems that would otherwise be too hard. It helps in real-world tasks like robot navigation, game moves, and network routing where many paths exist.

Where it fits

Before learning this, you should understand basic loops, arrays, and simple recursion. After this, you can learn more complex dynamic programming problems like grid obstacles, minimum path sums, or combinatorial path counting. This topic builds a foundation for solving many grid and path-related problems efficiently.

Mental Model

Core Idea

The number of unique paths to a cell is the sum of unique paths to the cell above it and the cell to its left.

Think of it like...

Imagine walking through a city grid where you can only move east or south. To reach any intersection, you can come either from the street above or the street to the left. The total ways to get there is just the sum of ways to get to those two places.

Grid with cells showing path counts:
┌───┬───┬───┐
│ 1 │ 1 │ 1 │
├───┼───┼───┤
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 1 │ 3 │ 6 │
└───┴───┴───┘
Each cell = paths from top + paths from left

Build-Up - 7 Steps

1

Foundation

Understanding the Grid Movement Rules

Concept: You can only move right or down in the grid from the start to the end.

Imagine a grid with rows and columns. You start at the top-left corner (0,0). At each step, you can move only one cell to the right or one cell down. You want to reach the bottom-right corner (m-1, n-1). No other moves are allowed.

Result

You know the allowed moves and the start and end points in the grid.

Knowing the movement rules sets the stage for counting paths because it limits possible directions, simplifying the problem.

2

Foundation

Brute Force Counting of Paths

Concept: Try all possible paths by exploring every move recursively.

Start at (0,0). At each cell, recursively move right or down until you reach the end. Count each successful path. For example, in a 2x2 grid, paths are: right->down and down->right.

Result

Number of paths for 2x2 grid is 2.

Brute force works for small grids but quickly becomes too slow as grid size grows because paths grow exponentially.

3

Intermediate

Introducing Dynamic Programming Table

Concept: Use a 2D table to store the number of paths to each cell to avoid repeated calculations.

Create a 2D array dp with the same size as the grid. Initialize the first row and first column to 1 because there's only one way to reach cells in those edges (all right or all down). For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1].

Result

dp table for 3x3 grid: 1 1 1 1 2 3 1 3 6

Storing results in a table prevents recalculating paths for the same cell multiple times, making the solution efficient.

4

Intermediate

Implementing DP in C# Code

Concept: Translate the DP logic into a working C# program using loops and arrays.

Use nested loops to fill the dp array. Start with dp[0,0] = 1. Fill first row and column with 1. Then fill each dp[i,j] by adding dp[i-1,j] and dp[i,j-1]. Return dp[m-1,n-1] as the answer.

Result

For a 3x3 grid, output is 6 unique paths.

Writing code solidifies understanding and shows how DP tables are built step-by-step.

5

Intermediate

Optimizing Space Usage

🤔Before reading on: Do you think we need to store the entire 2D table to find the answer, or can we use less memory? Commit to your answer.

Concept: Since each dp cell depends only on the current row and previous row, we can use a 1D array to save space.

Use a 1D array dp of size n (number of columns). Initialize all to 1. For each row from 1 to m-1, update dp[j] = dp[j] + dp[j-1]. This accumulates path counts for the current row.

Result

For 3x3 grid, dp array ends as [1,3,6], final answer 6.

Reducing space from O(m*n) to O(n) is important for large grids and shows how dependencies in DP can be exploited.

6

Advanced

Handling Obstacles in the Grid

🤔Before reading on: Do you think the same DP formula works if some cells are blocked? Commit to yes or no.

Concept: Modify DP to skip blocked cells by setting their path count to zero.

Given a grid with obstacles (cells you cannot pass), initialize dp cells to 0 if blocked. Otherwise, dp[i,j] = dp[i-1,j] + dp[i,j-1] only if the cell is free. This changes path counts accordingly.

Result

Paths count decreases when obstacles block some routes.

Adapting DP to obstacles shows flexibility and real-world applicability where paths may be restricted.

7

Expert

Mathematical Combinatorics Connection

🤔Before reading on: Is the number of unique paths in an empty grid related to combinations? Commit to yes or no.

Concept: The number of unique paths equals the number of ways to arrange moves right and down, which is a combination formula.

To reach bottom-right in m x n grid, you must move (m-1) downs and (n-1) rights in any order. Total moves = m+n-2. Number of unique paths = C(m+n-2, m-1) = (m+n-2)! / ((m-1)! (n-1)!). This matches DP results.

Result

For 3x3 grid, unique paths = C(4,2) = 6.

Understanding the combinatorial formula connects DP to math, offering a direct formula and deeper insight into the problem structure.

Under the Hood

The DP solution builds a table where each cell stores the count of unique paths to reach it. It uses the fact that to get to a cell, you must come from either the cell above or the cell to the left. By filling the table row by row or column by column, the algorithm accumulates counts without recalculating subproblems. This avoids exponential recursion and runs in O(m*n) time with O(m*n) or O(n) space.

Why designed this way?

Dynamic programming was designed to solve problems with overlapping subproblems and optimal substructure efficiently. The unique paths problem fits perfectly because each cell's solution depends only on two previous cells. Alternatives like brute force were too slow. The DP table approach balances simplicity, speed, and memory use.

┌───────────────┐
│ Start (0,0)   │
│ dp[0,0] = 1 │
└──────┬────────┘
       │
┌──────▼───────┐
│ dp[i,j] =   │
│ dp[i-1,j] + │
│ dp[i,j-1]   │
└──────┬───────┘
       │
┌──────▼───────┐
│ Fill table   │
│ row by row   │
└──────┬───────┘
       │
┌──────▼───────┐
│ Result at    │
│ dp[m-1,n-1] │
└──────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the number of unique paths changes if you can move diagonally? Commit yes or no.

Common Belief: The number of unique paths is the same regardless of allowed moves.

Reality: Allowing diagonal moves changes the problem and increases the number of unique paths, so the DP formula must change.

Why it matters: Using the standard DP formula with diagonal moves leads to wrong answers and misunderstandings of the problem.

Quick: Do you think initializing the first row and column with zeros is correct? Commit yes or no.

Common Belief: Setting the first row and column to zero is fine because no paths start there.

Reality: The first row and column must be set to 1 because there is exactly one way to reach those cells (all right or all down moves).

Why it matters: Incorrect initialization causes the entire DP table to have zeros, resulting in zero paths and wrong answers.

Quick: Do you think the DP solution always uses less memory than recursion? Commit yes or no.

Common Belief: DP always uses less memory than recursion.

Reality: Naive DP uses more memory for the table, but optimized recursion with memoization can use similar or less memory depending on implementation.

Why it matters: Assuming DP always saves memory can lead to ignoring recursion optimizations or choosing inefficient implementations.

Quick: Do you think the combinatorial formula works if obstacles are present? Commit yes or no.

Common Belief: The combinatorial formula applies even if some cells are blocked.

Reality: The formula only works for empty grids without obstacles. Obstacles require DP or other methods.

Why it matters: Using the formula with obstacles gives incorrect path counts, causing errors in real-world applications.

Expert Zone

1

The DP table can be computed in-place if the input grid is mutable, saving extra space.

2

When grid size is very large, using combinatorial formulas with modular arithmetic avoids overflow and speeds up computation.

3

In some cases, symmetry in the grid can reduce computation by calculating paths for half the grid and mirroring results.

When NOT to use

Avoid DP for unique paths when the grid is extremely large and only the count modulo a number is needed; use combinatorial formulas with modular arithmetic instead. Also, if diagonal or other moves are allowed, this DP approach must be adapted or replaced.

Production Patterns

In production, unique paths DP is used in robotics for path planning, in games for move counting, and in network routing algorithms to estimate route counts. It is often combined with obstacle handling and memory optimization for efficiency.

Connections

Pascal's Triangle

The DP table for unique paths forms values identical to Pascal's Triangle entries.

Recognizing this connection helps understand the combinatorial nature of the problem and allows using known mathematical properties.

Binomial Coefficients in Probability

Unique paths count is a binomial coefficient, which also appears in probability calculations for combinations.

Understanding binomial coefficients in probability deepens insight into counting problems and their formulas.

Urban Planning and Traffic Flow

Counting unique paths in a grid models how traffic can flow through city streets with intersections.

This real-world connection shows how abstract DP problems apply to designing efficient routes and managing congestion.

Common Pitfalls

#1 Incorrectly initializing the DP table's first row and column to zero.

Wrong approach:

for (int i = 0; i < m; i++) dp[i,0] = 0;
for (int j = 0; j < n; j++) dp[0,j] = 0;

Correct approach:

for (int i = 0; i < m; i++) dp[i,0] = 1;
for (int j = 0; j < n; j++) dp[0,j] = 1;

Root cause:

Misunderstanding that there is exactly one way to reach cells in the first row or column by moving only right or down.

#2 Using recursion without memoization causing exponential time.

Wrong approach:

int CountPaths(int i, int j) {
if (i == 0 && j == 0) return 1;
if (i < 0 || j < 0) return 0;
return CountPaths(i-1, j) + CountPaths(i, j-1);
}

Correct approach:

Use a dp array to store results:
int CountPaths(int m, int n) {
int[,] dp = new int[m,n];
// fill dp with base cases and loops
return dp[m-1,n-1];
}

Root cause:

Not storing intermediate results causes repeated calculations and slow performance.

#3 Ignoring obstacles and applying standard DP formula directly.

Wrong approach:

dp[i,j] = dp[i-1,j] + dp[i,j-1]; // without checking obstacles

Correct approach:

if (obstacleGrid[i,j] == 1) dp[i,j] = 0;
else dp[i,j] = dp[i-1,j] + dp[i,j-1];

Root cause:

Forgetting to handle blocked cells leads to counting invalid paths.

Key Takeaways

Unique Paths in Grid DP counts ways to reach the bottom-right cell by summing paths from above and left cells.

Dynamic programming avoids repeated work by storing intermediate results in a table or array.

Initializing the first row and column to 1 is crucial because there is only one way to reach those cells.

The problem connects deeply to combinatorics, where the number of paths equals a binomial coefficient.

Handling obstacles requires modifying the DP approach to skip blocked cells, showing DP's flexibility.

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