Dynamic Programming: Minimum/Maximum Falling Path Sum (DP on Grids)

1. Problem Statement & Context

This lecture explores the Maximum Falling Path Sum problem on a 2D grid, presenting a crucial generalization of grid dynamic programming.

Unlike previous problems that featured a fixed starting point (0, 0) and a fixed ending point (n - 1, m - 1), or a fixed start with a variable end, this problem features variable starting points AND variable ending points:

• Starting Point: Any cell in the first row (row 0).
• Ending Point: Any cell in the last row (row n - 1).
• Allowed Movements: From cell (i, j), you can move to:
  1. Directly below: (i - 1, j) (assuming we conceptualize the traversal bottom-up)
  2. Diagonally left: (i - 1, j - 1)
  3. Diagonally right: (i - 1, j + 1)

2. Why Greedy Fails: The Uniformity Law

You might initially wonder: Why not use a greedy approach by picking the maximum value at each step?

Real-Life Analogy / Mental Hook: Imagine navigating a landscape where making an immediate locally optimal choice (e.g., stepping onto a patch with $100$) forces you into a barren wasteland of negative values ($1, 1$), while an alternative local choice ($2$) leads you to a massive windfall further down ($20,000$).

Because grid values are not uniform and local maximums do not guarantee global optimality, Greedy fails completely. We must explore all paths to find the global optimum. This requires Recursion and Dynamic Programming.

3. The Recursive Formulation (Top-Down Mental Model)

When designing a recurrence relation for grids with variable endpoints, we invert our perspective:

• Instead of starting at the top and searching everywhere below, we start by targeting every cell in the last row and working our way up to the first row.
• Let f(i, j) be defined as:

  The maximum path sum to reach cell (i, j) starting from any cell in the first row (row 0).

The Three Steps of Recursion:

1. Express in terms of indices (i, j) & Base Cases: Handle boundaries and the destination row (i == 0).
2. Explore all paths: Try moving straight up, diagonally left-up, and diagonally right-up.
3. Return the maximum: Take max() across all explored paths.

4. Naive Recursive Approach & Code

We can write a pure recursive function that explores all $3^n$ possible paths (exponential time complexity).

Recursive C++ Implementation

int f(int i, int j, vector<vector<int>>& matrix) {
    // Base Cases: Out of bounds
    if (j < 0 || j >= matrix[0].size()) return -1e9; // Return very small number for MAX problems
    
    // Base Case: Reached the first row (destination)
    if (i == 0) return matrix[0][j];

    // Explore 3 possible directions moving upwards
    int up = matrix[i][j] + f(i - 1, j, matrix);
    int leftDiagonal = matrix[i][j] + f(i - 1, j - 1, matrix);
    int rightDiagonal = matrix[i][j] + f(i - 1, j + 1, matrix);

    return max({up, leftDiagonal, rightDiagonal});
}

// Main caller for variable starting/ending points
int getMaxPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    int maxi = -1e9;

    // Try ending at every column of the last row
    for (int j = 0; j < m; j++) {
        maxi = max(maxi, f(n - 1, j, matrix));
    }
    return maxi;
}

5. Overlapping Subproblems & Memoization

When evaluating multiple starting columns across the last row, the same subproblems f(i, j) are computed repeatedly. We can eliminate redundant work using Memoization with a 2D DP table of size N x M.

Memoized C++ Implementation

int f(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& dp) {
    if (j < 0 || j >= matrix[0].size()) return -1e9;
    if (i == 0) return matrix[0][j];
    
    if (dp[i][j] != -1) return dp[i][j];

    int up = matrix[i][j] + f(i - 1, j, matrix, dp);
    int leftDiagonal = matrix[i][j] + f(i - 1, j - 1, matrix, dp);
    int rightDiagonal = matrix[i][j] + f(i - 1, j + 1, matrix, dp);

    return dp[i][j] = max({up, leftDiagonal, rightDiagonal});
}

• Time Complexity: $O(N \times M)$ states.
• Space Complexity: $O(N \times M)$ DP Table + $O(N)$ Recursion Stack Space.

6. Tabulation (Bottom-Up Approach)

To avoid recursion stack overflow and auxiliary stack overhead, we convert the top-down memoized solution into a bottom-up tabulation approach.

Tabulation Workflow:

1. Initialize DP Table: Create a dp[n][m] table initialized to 0.
2. Base Case: Fill the first row (i = 0) directly from the matrix: dp[0][j] = matrix[0][j].
3. Iterate Grids: Loop i from 1 to n - 1 and j from 0 to m - 1.
4. Apply Recurrence with Bounds Check:
   • up = matrix[i][j] + dp[i - 1][j]
   • leftDiagonal = matrix[i][j] + (j - 1 >= 0 ? dp[i - 1][j - 1] : -1e9)
   • rightDiagonal = matrix[i][j] + (j + 1 < m ? dp[i - 1][j + 1] : -1e9)

Tabulation C++ Code

int getMaxPathSumTab(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));

    // Base Case: First row
    for (int j = 0; j < m; j++) {
        dp[0][j] = matrix[0][j];
    }

    // Bottom-up traversal
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int up = matrix[i][j] + dp[i - 1][j];
            
            int leftDiag = matrix[i][j];
            if (j - 1 >= 0) leftDiag += dp[i - 1][j - 1];
            else leftDiag += -1e9;

            int rightDiag = matrix[i][j];
            if (j + 1 < m) rightDiag += dp[i - 1][j + 1];
            else rightDiag += -1e9;

            dp[i][j] = max({up, leftDiag, rightDiag});
        }
    }

    // Find maximum across the last row
    int maxi = -1e9;
    for (int j = 0; j < m; j++) {
        maxi = max(maxi, dp[n - 1][j]);
    }
    return maxi;
}

7. Space Optimization

Notice that to compute the current row i, our recurrence only ever looks back at the immediately preceding row i - 1. We do not need the entire N x M matrix!

Optimization Strategy:

• Maintain two 1D arrays: prev (representing row i - 1) and curr (representing row i).
• After completing row v, assign prev = curr before moving to the next row.

Space-Optimized C++ Code

int getMaxPathSumSpaceOptimized(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();

    vector<int> prev(m, 0), curr(m, 0);

    // Base Case: First row
    for (int j = 0; j < m; j++) {
        prev[j] = matrix[0][j];
    }

    // Iterate row by row
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int up = matrix[i][j] + prev[j];
            
            int leftDiag = matrix[i][j];
            if (j - 1 >= 0) leftDiag += prev[j - 1];
            else leftDiag += -1e9;

            int rightDiag = matrix[i][j];
            if (j + 1 < m) rightDiag += prev[j + 1];
            else rightDiag += -1e9;

            curr[j] = max({up, leftDiag, rightDiag});
        }
        prev = curr; // Shift rows
    }

    // Find maximum in the last computed row (prev)
    int maxi = -1e9;
    for (int j = 0; j < m; j++) {
        maxi = max(maxi, prev[j]);
    }
    return maxi;
}

8. Complexity Analysis Summary

9. Summary and Key Takeaways

• Variable Start & End Points: When starting points and ending points span across entire rows or columns, evaluate results across all candidate cells in the target row/column.
• Inverting the Perspective: Solving bottom-up (from the last row to the first row) simplifies tracking trajectories and matches standard grid recurrences.
• Greedy Inadequacy: Non-uniform grid weights prevent greedy selection; dynamic programming is necessary to evaluate all path alternatives.
• Out-of-Bound Penalty: When computing max() paths, out-of-bound indices must return an extremely small value (e.g., -1e9) so they are naturally ignored.
• Space Reduction Principle: Since state transitions only depend on the previous row (i - 1), the space complexity can be reduced from $O(N \times M)$ down to $O(M)$ using 1D arrays (prev and curr).