Unique Paths in Grid DP in DSA Java - 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 answers to smaller parts of the problem so it doesn't repeat work. This method helps solve problems where you want to find the number of possible routes in a grid-like path.

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 makes the problem fast and practical, which is important in areas like robotics, games, and navigation systems.

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 sum, or combinatorial path counting.

Mental Model

Core Idea

The number of ways to reach a cell is the sum of ways to reach the cell above it and the cell to the left.

Think of it like...

Imagine walking through a city grid where you can only move east or south. To get to any intersection, you can come from the intersection above or the one to the left. Counting all ways to reach an intersection is like adding the ways you could have arrived from those two directions.

Start (0,0)
  ↓       ->
(0,0) -> (0,1) -> (0,2) -> ... -> (0,n-1)
  ↓       ↓       ↓             ↓
(1,0) -> (1,1) -> (1,2) -> ... -> (1,n-1)
  ↓       ↓       ↓             ↓
...     ...     ...           ...
  ↓       ↓       ↓             ↓
(m-1,0)->(m-1,1)->(m-1,2)-> ... ->(m-1,n-1) End

Build-Up - 7 Steps

1

Foundation

Understanding the Grid and Moves

Concept: Introduce the grid layout and allowed moves (right and down).

Imagine a grid with m rows and n columns. You start at the top-left corner (0,0) and want to reach the bottom-right corner (m-1,n-1). You can only move one step right or one step down at a time. The question is: how many different paths can you take?

Result

You know the problem setup and allowed moves.

Understanding the problem constraints is key before solving it.

2

Foundation

Brute Force Counting Paths

Concept: Count paths by trying all possible moves recursively.

You can try every possible path by moving right or down until you reach the end. For each step, you explore two options: move right or move down. If you reach the bottom-right corner, count 1 path. If you go outside the grid, count 0.

Result

The total count is the sum of all valid paths.

This method works but is very slow because it repeats the same calculations many times.

3

Intermediate

Introducing Dynamic Programming Table

🤔Before reading on: do you think storing intermediate results will speed up counting paths? Commit to yes or no.

Concept: Use a table to store the number of ways to reach each cell to avoid repeated work.

Create a 2D array dp with the same size as the grid. dp[i][j] will store the number of unique paths to reach cell (i,j). Initialize dp[0][0] = 1 because there is only one way to start. Then fill the table row by row or column by column using the rule: dp[i][j] = dp[i-1][j] + dp[i][j-1], where dp[i-1][j] is ways from above and dp[i][j-1] is ways from left.

Result

You get a filled table where dp[m-1][n-1] is the total number of unique paths.

Storing results for each cell prevents repeated calculations and makes the solution efficient.

4

Intermediate

Handling Edge Cases in DP Table

🤔Before reading on: do you think the first row and first column need special handling? Commit to yes or no.

Concept: First row and first column have only one way to reach each cell because you can only move right or down respectively.

For the first row, dp[0][j] = 1 for all j because you can only move right from the start. For the first column, dp[i][0] = 1 for all i because you can only move down. This sets the base cases for the DP table.

Result

The DP table is correctly initialized and ready for filling.

Properly setting base cases ensures the DP formula works correctly for all cells.

5

Intermediate

Implementing DP Solution in Java

🤔Before reading on: do you think the DP solution will run in O(m*n) time? Commit to yes or no.

Concept: Translate the DP logic into Java code with nested loops.

Use two nested loops to fill dp array. Outer loop for rows i from 0 to m-1, inner loop for columns j from 0 to n-1. Initialize first row and column to 1. For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1]. Return dp[m-1][n-1] as the answer.

Result

The code runs efficiently and returns the correct number of unique paths.

Understanding the time complexity helps appreciate the efficiency gain over brute force.

6

Advanced

Optimizing Space Usage in DP

🤔Before reading on: can we reduce the 2D dp array to a 1D array? Commit to yes or no.

Concept: Since dp[i][j] depends only on dp[i-1][j] and dp[i][j-1], we can use a single array to save space.

Use a 1D array dp of size n. Initialize all elements to 1 for the first row. For each subsequent row, update dp[j] = dp[j] + dp[j-1]. This way, dp[j] holds the number of ways to reach cell (i,j).

Result

The solution uses O(n) space instead of O(m*n) and still returns the correct answer.

Knowing how to optimize space is important for large grids and memory-limited environments.

7

Expert

Mathematical Combinatorics Approach

🤔Before reading on: do you think the number of unique paths can be calculated without DP using math? Commit to yes or no.

Concept: The problem can be solved using combinations because each path is a sequence of moves right and down.

To reach from (0,0) to (m-1,n-1), you must move (m-1) times down and (n-1) times right in any order. Total moves = (m-1)+(n-1) = m+n-2. The number of unique paths is the number of ways to choose positions for either down or right moves, which is C(m+n-2, m-1) or C(m+n-2, n-1).

Result

You get a direct formula to calculate unique paths without building a DP table.

Understanding the combinatorial formula connects DP to math and offers an alternative efficient solution.

Under the Hood

The DP solution builds a table where each cell stores the count of unique paths to that cell. It uses previously computed results from the top and left neighbors to avoid redundant calculations. This bottom-up approach fills the table systematically until the destination cell is reached.

Why designed this way?

Dynamic programming was designed to solve problems with overlapping subproblems and optimal substructure efficiently. Counting unique paths fits this pattern because the number of ways to a cell depends only on its neighbors. Alternatives like brute force were too slow, and pure combinatorics may not work with obstacles or variations.

┌─────────────┐
│ Start (0,0) │
└─────┬───────┘
      │
┌─────▼───────┐
│ dp Table    │
│ +---------+ │
│ |1 1 1 1 1| │
│ |1 2 3 4 5| │
│ |1 3 6 10 15|│
│ +---------+ │
└─────────────┘
Each cell = sum of top + left

Myth Busters - 3 Common Misconceptions

Quick: Do you think the number of unique paths depends on the order of moves or just the count? Commit to order or count.

Common Belief: People often think the order of moves matters for counting unique paths.

Reality: Only the count of moves right and down matters, not the order. Different orders represent different paths, but the DP counts all possible orders correctly.

Why it matters: Misunderstanding this can lead to wrong formulas or ignoring valid paths.

Quick: Do you think the DP table must be fully filled before getting any answer? Commit to yes or no.

Common Belief: Some believe you must fill the entire DP table before knowing any partial results.

Reality: You can compute partial results as you fill the table row by row or column by column, and intermediate results are valid counts for subproblems.

Why it matters: Knowing this helps optimize and debug DP solutions by checking intermediate states.

Quick: Do you think the combinatorial formula works for grids with obstacles? Commit to yes or no.

Common Belief: Many think the combinatorial formula applies even if some cells are blocked.

Reality: The formula only works for empty grids without obstacles. With obstacles, DP is needed to account for blocked paths.

Why it matters: Using the formula blindly leads to incorrect answers in real-world problems with obstacles.

Expert Zone

1

The DP solution's time complexity is O(m*n), but the space can be optimized to O(n) by reusing a single array.

2

The combinatorial formula is a closed-form solution but does not extend to variations like obstacles or weighted paths.

3

DP solutions can be adapted to count paths with constraints by modifying the state and transition rules.

When NOT to use

Avoid using the combinatorial formula when the grid has obstacles or special rules. Instead, use DP or graph traversal algorithms like BFS or DFS. For very large grids where memory is limited, consider space-optimized DP or mathematical approximations.

Production Patterns

In production, unique paths DP is used in robotics for path planning, in games for movement options, and in network routing algorithms. Space optimization and handling obstacles are common extensions. Memoization and iterative DP are preferred over recursion for performance.

Connections

Pascal's Triangle

The DP table for unique paths mirrors Pascal's Triangle values.

Recognizing this connection helps understand the combinatorial nature of the problem and how binomial coefficients appear in DP.

Graph Theory

The grid can be seen as a directed graph where edges go right or down.

Viewing the problem as counting paths in a graph broadens understanding and connects to algorithms like BFS and DFS.

Probability Theory

Counting unique paths relates to counting outcomes in probability spaces.

Understanding path counting helps in calculating probabilities of sequences of events with constraints.

Common Pitfalls

#1 Not initializing the first row and first column correctly.

Wrong approach:

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) dp[i][j] = 1;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}

Correct approach:

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];
}
}

Root cause:

Trying to apply the DP formula without setting base cases causes index errors and wrong counts.

#2 Using recursion without memoization leading to slow performance.

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 i, int j, int[][] dp) {
if (i == 0 && j == 0) return 1;
if (i < 0 || j < 0) return 0;
if (dp[i][j] != -1) return dp[i][j];
dp[i][j] = countPaths(i-1, j, dp) + countPaths(i, j-1, dp);
return dp[i][j];
}

Root cause:

Not storing intermediate results causes exponential time complexity.

#3 Applying combinatorial formula directly on grids with obstacles.

Wrong approach:

int uniquePaths = combination(m + n - 2, m - 1); // ignoring obstacles

Correct approach:

Use DP to check for obstacles and count paths accordingly.

Root cause:

Misunderstanding problem constraints leads to incorrect solutions.

Key Takeaways

Unique Paths in Grid DP counts all ways to reach the bottom-right corner by moving only right or down.

Dynamic programming efficiently solves this by building a table of partial results to avoid repeated work.

Proper initialization of the first row and column is crucial for correct DP computation.

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

Space optimization and handling obstacles are important extensions for real-world applications.

Practice

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

easy

A. The maximum sum path from top-left to bottom-right in a grid

B. The shortest path length from top-left to bottom-right in a grid

C. The number of obstacles in the grid

D. The number of ways to move from top-left to bottom-right in a grid moving only right or down

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the correct interpretation

   Among the options, only counting the number of ways to move right or down matches the problem description.

3. Final Answer:

   The number of ways to move from top-left to bottom-right in a grid moving only right or down -> Option D

4. Quick Check:

   Unique Paths = Counting ways moving right/down [OK]

Hint: Unique Paths count moves right/down only [OK]

Common Mistakes:

• Confusing unique paths with shortest path
• Thinking about obstacles instead of paths
• Mixing path count with path sum

2. Which of the following Java code snippets correctly initializes a 2D DP array dp for a grid of size m x n?

easy

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

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

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

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

Solution

1. Step 1: Recall Java 2D array syntax

   In Java, a 2D array is declared as int[][] dp = new int[m][n]; where m is rows and n is columns.

2. Step 2: Check each option

   int[][] dp = new int[m][n]; matches correct syntax. int dp[][] = new int[n][m]; swaps dimensions. int dp = new int[m][n]; uses wrong type. int[][] dp = new int[m]; misses second dimension.

3. Final Answer:

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

4. Quick Check:

   Java 2D array = int[][] dp = new int[m][n] [OK]

Hint: Use int[][] dp = new int[m][n] for 2D arrays [OK]

Common Mistakes:

• Swapping row and column sizes
• Missing second dimension in array creation
• Using single brackets for 2D arrays

3. What is the output of the following Java code snippet for m = 3 and n = 3?

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];
  }
}
System.out.println(dp[m-1][n-1]);

medium

A. 3

B. 10

C. 6

D. 1

Solution

1. Step 1: Initialize first row and column

   First row and first column are set to 1, representing only one way to reach those cells.

2. Step 2: Fill dp table using sum of top and left cells

   Calculate dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2, dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3, dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3, dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6.

3. Step 3: Recalculate final cell

   dp[2][2] = 6 is incorrect for 3x3 grid unique paths. The correct number of unique paths in a 3x3 grid is 6, but let's verify carefully:
   Actually, the number of unique paths from top-left to bottom-right in a 3x3 grid moving only right or down is 6.
   Let's trace the dp table:
   Row 0: [1,1,1]
   Row 1: [1,2,3]
   Row 2: [1,3,6]
   So dp[2][2] = 6 is correct.

4. Final Answer:

   6 -> Option C

5. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum ways from top and left cells to fill dp [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding dp[i][j-1] and dp[i-1][j] incorrectly
• Off-by-one errors in loops

4. Identify the bug in the following Java code for computing unique paths in an m x n grid:

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];
  }
}

medium

A. Loops use <= causing ArrayIndexOutOfBoundsException

B. dp array is not initialized

C. Sum formula is incorrect

D. No bug, code is correct

Solution

1. Step 1: Check loop boundaries for dp array

   Arrays in Java are 0-indexed, so valid indices are 0 to m-1 and 0 to n-1. Using <= m or <= n causes index out of bounds.

2. Step 2: Identify the error cause

   Loops with condition i <= m and j <= n try to access dp[m][0] or dp[0][n], which do not exist.

3. Final Answer:

   Loops use <= causing ArrayIndexOutOfBoundsException -> Option A

4. Quick Check:

   Array indices must be less than size [OK]

Hint: Use < not <= for array indices in loops [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring zero-based indexing
• Assuming array size includes upper bound index

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?
Choose the correct approach:

hard

A. Use recursion without memoization to handle obstacles

B. Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], Initialize dp[0][0] = 1 if no obstacle, Handle first row and column carefully considering obstacles

C. Set dp[i][j] = 1 if grid[i][j] == 1; else 0, Sum all dp values at the end

D. Ignore obstacles and calculate paths normally, Obstacles don't affect path count

Solution

1. Step 1: Understand obstacle effect on paths

   If a cell has an obstacle, no path can go through it, so dp value must be 0.

2. Step 2: Modify DP formula and initialization

   Set dp[i][j] = 0 if obstacle; else sum of dp from top and left. Initialize dp[0][0] = 1 only if no obstacle. First row and column must consider obstacles to stop paths beyond them.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], Initialize dp[0][0] = 1 if no obstacle, Handle first row and column carefully considering obstacles -> Option B

4. Quick Check:

   Obstacles block paths, dp=0 there [OK]

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

Common Mistakes:

• Ignoring obstacles in dp calculation
• Not initializing dp[0][0] correctly
• Not stopping path count after obstacle in first row/column