Master DSA: Minimum Path Sum (2D Dynamic Programming)

This chapter explores the transition from 1D to 2D Dynamic Programming (DP) using the classic Minimum Path Sum problem. We will analyze the core mental models of 2D grid navigation and systematically evolve our solution through three distinct DP paradigms: Recursion with Memoization (Top-Down), Tabulation (Bottom-Up), and Space Optimization (1D Rolling Array).

1. The Core Problem: Navigating a 2D Grid

The Minimum Path Sum problem provides an $m \times n$ grid filled with non-negative integers. The objective is to find a path from the top-left corner $(0, 0)$ to the bottom-right corner $(m-1, n-1)$ that minimizes the sum of all numbers along its path.

Constraints & Movement Rules

• You can only move either down or right at any point in time.
• All numbers in the grid are non-negative.

Visualizing the Grid and Path

Consider the following $3 \times 3$ grid:

Row 0: [ 1,  3,  1 ]
Row 1: [ 1,  5,  1 ]
Row 2: [ 4,  2,  1 ]

The path with the minimum sum is highlighted below:

• Path: $1 \to 3 \to 1 \to 1 \to 1$
• Minimum Sum: $1 + 3 + 1 + 1 + 1 = 7$

2. The Mental Model: Top-Down Decisions

To solve this problem using Dynamic Programming, we must break it down into smaller subproblems.

The Backward-Looking Intuition

Instead of asking "Where do we go from the start?", we ask: "How did we reach our final destination cell $(i, j)$?"

Because we can only move down or right, any cell $(i, j)$ can only be reached from two possible directions:

1. From the Top: The cell directly above it, located at $(i-1, j)$.
2. From the Left: The cell directly to its left, located at $(i, j-1)$.

To find the minimum path sum to reach $(i, j)$, we take the minimum of the path sums required to reach its two valid neighbors, and then add the value of the current cell:

3. The Recursive Flow & Decision Tree

When we implement this top-down approach recursively, we start at the destination $(m-1, n-1)$ and branch backward toward the origin $(0, 0)$.

Recursive Decision Flow

Note: Notice that the subproblem $(m-2, n-2)$ is reached through multiple paths. In a naive recursive approach, this state is recomputed repeatedly, leading to an exponential time complexity of $O(2^{m+n})$. This redundant computation is the exact problem that Dynamic Programming solves.

4. Approach 1: Recursion with Memoization (Top-Down)

To prevent redundant calculations, we introduce a 2D array dp of size $m \times n$, initialized to -1. When a state $(i, j)$ is computed for the first time, we store its result in dp[i][j]. On subsequent visits, we return the cached value instantly.

Base Cases

1. Origin Reached: If $i = 0$ and $j = 0$, we have reached the starting point. We return grid[0][0].
2. Out of Bounds: If $i < 0$ or $j < 0$, we have stepped off the grid. Since we want to minimize the path sum, we return an extremely large value (Integer.MAX_VALUE) so that this invalid path is never chosen during the Math.min() comparison.

Java Implementation

import java.util.Arrays;

public class MinimumPathSumMemoization {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        // Initialize DP table with -1 to represent uncomputed states
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        
        return helper(m - 1, n - 1, grid, dp);
    }
    
    private int helper(int i, int j, int[][] grid, int[][] dp) {
        // Base Case 1: Starting point reached
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        
        // Base Case 2: Out of bounds
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }
        
        // Return cached result if already calculated
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        
        // Recursive calls for Top and Left paths
        int top = helper(i - 1, j, grid, dp);
        int left = helper(i, j - 1, grid, dp);
        
        // Store and return the minimum path sum for the current cell
        dp[i][j] = grid[i][j] + Math.min(top, left);
        return dp[i][j];
    }
}

Complexity Analysis

• Time Complexity: $O(m \times n)$ — There are $m \times n$ unique states. Each state is computed exactly once due to memoization.
• Space Complexity: $O(m \times n) + O(m + n)$ — $O(m \times n)$ space is used by the 2D dp array, and $O(m + n)$ space is used by the recursive call stack.

5. Tracing the DP Table Construction

To transition to the iterative bottom-up approach, let us manually trace how the DP table is filled for our sample grid:

Grid:
1  3  1
1  5  1
4  2  1

We fill the DP table cell-by-cell, starting from $(0,0)$:

1. Cell $(0,0)$: Base case.

2. Cell $(0,1)$: No top neighbor exists. We can only come from the left.

3. Cell $(0,2)$: Only left neighbor exists.

4. Cell $(1,0)$: Only top neighbor exists.

5. Cell $(1,1)$: Both top and left neighbors exist.

6. Cell $(1,2)$: Both top and left neighbors exist.

7. Cell $(2,0)$: Only top neighbor exists.

8. Cell $(2,1)$: Both top and left neighbors exist.

9. Cell $(2,2)$: Both top and left neighbors exist.

Final DP Table State

6. Approach 2: Tabulation (Bottom-Up DP)

Tabulation eliminates the overhead of recursion by iteratively filling the 2D dp table using nested loops.

Handling Boundaries Iteratively

To handle cells in the first row ($i = 0$) and first column ($j = 0$) without throwing ArrayIndexOutOfBoundsException, we check if the indices are greater than zero before accessing the DP table. If they are not, we substitute Integer.MAX_VALUE for the missing neighbor.

Java Implementation

public class MinimumPathSumTabulation {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Base Case: Starting point
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else {
                    // If i > 0, get top value; else use infinity
                    int up = (i > 0) ? dp[i - 1][j] : Integer.MAX_VALUE;
                    
                    // If j > 0, get left value; else use infinity
                    int left = (j > 0) ? dp[i][j - 1] : Integer.MAX_VALUE;
                    
                    dp[i][j] = grid[i][j] + Math.min(up, left);
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

Complexity Analysis

• Time Complexity: $O(m \times n)$ — Two nested loops traverse the entire grid.
• Space Complexity: $O(m \times n)$ — Used to store the 2D dp table. The recursive call stack is eliminated.

7. The Space Optimization Breakthrough

If we analyze the iterative transition formula:

We can observe a critical dependency pattern:

• dp[i-1][j] represents the cell directly above in the previous row.
• dp[i][j-1] represents the cell directly to the left in the current row.

To calculate any cell in the current row, we only need:

1. The corresponding column value from the immediate previous row (prev[j]).
2. The newly calculated value to its immediate left in the same row (curr[j-1]).

We do not need any rows above $i-1$. Therefore, we can discard all older rows and maintain only two 1D arrays of size $n$:

• prev: Stores the results of the previous row.
• curr: Stores the results of the current row being calculated.

8. Approach 3: Space-Optimized 1D DP

By replacing the 2D grid with two 1D arrays, we reduce the auxiliary space complexity from quadratic to linear.

Java Implementation

public class MinimumPathSumSpaceOptimized {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        // Array to store results of the previous row
        int[] prev = new int[n];
        
        for (int i = 0; i < m; i++) {
            // Array to store results of the current row
            int[] curr = new int[n];
            
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    curr[j] = grid[i][j];
                } else {
                    // Up value comes from the previous row's j-th column
                    int up = (i > 0) ? prev[j] : Integer.MAX_VALUE;
                    
                    // Left value comes from the current row's (j-1)-th column
                    int left = (j > 0) ? curr[j - 1] : Integer.MAX_VALUE;
                    
                    curr[j] = grid[i][j] + Math.min(up, left);
                }
            }
            // Move current row to previous row for the next iteration
            prev = curr;
        }
        
        return prev[n - 1];
    }
}

Complexity Analysis

• Time Complexity: $O(m \times n)$ — We still visit every cell in the grid exactly once.
• Space Complexity: $O(n)$ — We only maintain two 1D arrays of size $n$ (where $n$ is the number of columns).

9. Comparative Synthesis of the Three Approaches

10. Common Pitfalls & Debugging Workflows

1. Integer Overflow with Integer.MAX_VALUE

When writing recursive base cases or boundary conditions, returning Integer.MAX_VALUE is a common way to represent an invalid path. However, if you add a positive value to Integer.MAX_VALUE, it will overflow and wrap around to a negative number (e.g., Integer.MAX_VALUE + 1 = Integer.MIN_VALUE).

• The Bug:
  JAVA

  Copy

  int top = helper(i - 1, j, grid, dp); // Returns Integer.MAX_VALUE
  int ans = grid[i][j] + top; // Overflow occurs here!
  

• The Fix: Always perform boundary checks before adding, or use a safe "infinity" value like 1e9 (1,000,000,000) which is larger than any possible path sum but small enough to prevent overflow when added to grid values.

2. Incorrect Array Initialization

In the space-optimized approach, forgetting to copy curr to prev at the end of each row iteration will cause subsequent rows to use outdated or zero-initialized values.

• The Fix: Ensure prev = curr; is executed immediately after the inner column loop finishes and before the next row iteration begins.

11. Summary and Key Takeaways

• 2D DP Transition: Moving from 1D to 2D DP involves tracking two state variables (typically row index i and column index j) instead of one.
• Directional Constraints: The movement rules (only down or right) dictate that any cell $(i, j)$ depends strictly on its top neighbor $(i-1, j)$ and left neighbor $(i, j-1)$.
• Memoization Cache: Initializing the DP cache with -1 allows the algorithm to distinguish between uncalculated states and states that have a calculated path sum of 0.
• Iterative Tabulation: Tabulation builds solutions from the smallest subproblem $(0,0)$ up to the target $(m-1, n-1)$, eliminating recursive stack overhead.
• Boundary Substitution: Using ternary operators to substitute Integer.MAX_VALUE for out-of-bounds neighbors keeps the transition logic clean and readable.
• Space Optimization Rule: If a DP transition formula only references the current row and the immediate previous row, the space complexity can always be optimized from $O(m \times n)$ to $O(n)$.