Why Unique Paths in Grid DP in DSA Java?

The Big Idea

What if you could instantly know all possible routes in a maze without walking them?

The Scenario

Imagine you are in a big city grid and want to walk from your home at the top-left corner to your friend's house at the bottom-right corner. You can only walk right or down. Counting all possible ways by hand is like listing every single path on a huge map.

The Problem

Trying to count all paths manually is slow and confusing. As the grid grows, the number of paths grows very fast, making it impossible to keep track without mistakes. It's like trying to count every grain of sand on a beach.

The Solution

Dynamic Programming helps by breaking the problem into smaller parts. It remembers the number of ways to reach each cell, so it doesn't repeat counting the same paths again and again. This saves time and effort, making the problem easy to solve even for big grids.

Before vs After

✗ Before

int countPaths(int row, int col) {
  if (row == 0 && col == 0) return 1;
  if (row < 0 || col < 0) return 0;
  return countPaths(row - 1, col) + countPaths(row, col - 1);
}

✓ After

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

What It Enables

This concept lets you quickly find the number of ways to reach any point in a grid, even when the grid is very large.

Real Life Example

Delivery robots in a warehouse use this idea to find how many different routes they can take to deliver packages efficiently without backtracking.

Key Takeaways

Manual counting of paths is slow and error-prone.

Dynamic Programming stores results to avoid repeated work.

It makes counting paths in grids fast and easy.

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