DP 10: Minimum Path Sum in Grid

This chapter explores the third core problem on dynamic programming over 2D grids: Minimum Path Sum. Building directly upon previous grid traversal foundations (specifically Lecture 8), this problem introduces non-uniform cost routing where a greedy strategy completely fails, requiring a robust recursive exploration backed by memoization, tabulation, and space optimization.

1. Problem Statement & Real-World Context

• The Scenario: Imagine a country named Ninja Land represented as a 2D grid with $N$ rows and $M$ columns. Each cell $(i, j)$ contains a specific cost.
• The Objective: Start from the top-left cell (0, 0) and travel to the bottom-right cell (N - 1, M - 1) while strictly moving only right or only down.
• The Constraint: Find a path that minimizes the sum of all costs encountered along the way and return that minimum sum.
• Interview Relevance: This exact problem was featured in a Microsoft internship interview, highlighting its importance in coding evaluations.

2. Why a Greedy Approach Fails

When faced with path-finding problems, beginners often attempt a greedy strategy—always picking the adjacent cell with the smaller immediate cost. However, greedy algorithms fail when grid values lack uniformity.

Real-Life Analogy: The Deceptive Toll Road

Imagine driving through a network of roads. You choose the cheaper toll booth right now, but it abruptly leads you onto an extremely expensive highway network downstream, whereas taking a slightly more expensive road initially would have bypassed heavy tolls later.

Consider this grid example:

• A greedy choice at the start forces you from 10 to 8, then to 2, but traps you into moving to 100 (total cost explodes).
• A non-greedy path could yield a significantly smaller overall cost because today's local decision severely impacts tomorrow's global cost. Therefore, we must evaluate all possible paths, which points directly to recursion.

3. Step 1: Formulating the Recursive Solution

To solve this via recursion, we apply the foundational three-rule framework for dynamic programming on grids:

1. Express the problem in terms of indexes: Define a function $F(i, j)$ that returns the minimum path sum to reach cell $(i, j)$ starting from (0, 0). Thus, our final answer is $F(N - 1, M - 1)$.
2. Explore all paths: From any cell $(i, j)$, we can arrive either from the top (i - 1, j) or from the left (i, j - 1). Because we are solving it in reverse (moving backwards from the destination to (0, 0)), our recursive calls look up and left.
3. Take the minimum: Choose the path with the minimum accumulated cost.

Recursive Function Code (Naive)

int f(int i, int j, vector<vector<int>>& grid) {
    // Base Case 1: Reached the origin (0, 0)
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    
    // Base Case 2: Out of bounds
    if (i < 0 || j < 0) {
        return 1e9; // Return a very large number so this path is ignored in min()
    }
    
    // Recursive choices: Move up or move left
    int up = grid[i][j] + f(i - 1, j, grid);
    int left = grid[i][j] + f(i, j - 1, grid);
    
    return min(up, left);
}

4. Step 2: Memoization (Top-Down DP)

The naive recursive solution recomputes overlapping subproblems repeatedly, resulting in an exponential time complexity $O(2^{N \times M})$. We eliminate this redundancy by introducing a memoization table (dp array) initialized to -1.

Memoized Code Implementation

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    int f(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& dp) {
        if (i == 0 && j == 0) return grid[0][0];
        if (i < 0 || j < 0) return 1e9;
        
        // Return cached result if already computed
        if (dp[i][j] != -1) return dp[i][j];
        
        int up = grid[i][j] + f(i - 1, j, grid, dp);
        int left = grid[i][j] + f(i, j - 1, grid, dp);
        
        return dp[i][j] = min(up, left);
    }

public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return f(n - 1, m - 1, grid, dp);
    }
};

• Time Complexity: $O(N \times M)$ because each state is computed once.
• Space Complexity: $O(N \times M)$ for the dp table $+ O(N + M)$ for the recursion stack space.

5. Step 3: Tabulation (Bottom-Up DP)

We can convert the top-down memoized solution into an iterative, bottom-up tabulated format to eliminate recursion stack overhead.

Tabulated Code Implementation

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else {
                    int up = grid[i][j];
                    if (i > 0) up += dp[i - 1][j];
                    else up += 1e9; // Out of bounds penalty
                    
                    int left = grid[i][j];
                    if (j > 0) left += dp[i][j - 1];
                    else left += 1e9; // Out of bounds penalty
                    
                    dp[i][j] = min(up, left);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

• Time Complexity: $O(N \times M)$
• Space Complexity: $O(N \times M)$ for the explicit 2D table.

6. Step 4: Space Optimization

Notice that computing the current row's values (dp[i][j]) only requires:

1. The value directly above from the previous row (dp[i - 1][j]).
2. The value immediately to the left in the current row (dp[i][j - 1]).

We do not need an entire $N \times M$ matrix; tracking just the previous row and the current row is sufficient.

Space-Optimized Code Implementation

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        vector<int> prev(m, 0);
        
        for (int i = 0; i < n; i++) {
            vector<int> curr(m, 0);
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) {
                    curr[j] = grid[i][j];
                } else {
                    int up = grid[i][j];
                    if (i > 0) up += prev[j];
                    else up += 1e9;
                    
                    int left = grid[i][j];
                    if (j > 0) curr[j - 1] // Note: left relies on current row's previous col
                    // Let's reference curr[j-1] properly:
                    // curr[j] = min(up, left)
                    
                    // Correct implementation snippet:
                    int leftVal = grid[i][j];
                    if (j > 0) leftVal += curr[j - 1];
                    else leftVal += 1e9;
                    
                    curr[j] = min(up, leftVal);
                }
            }
            prev = curr; // Shift current row to previous for the next iteration
        }
        return prev[m - 1];
    }
};

• Time Complexity: $O(N \times M)$
• Space Complexity: $O(M)$ where $M$ is the number of columns.

7. Summary and Key Takeaways

• Problem Nature: Finding optimal paths in grids with variable costs requires exploring all valid paths.
• Why Greedy Fails: Non-uniform grid values mean short-term cheap choices can lead to catastrophic long-term costs.
• Recursive State Definition: Express states using 2D coordinates (i, j) representing the minimum cost from (0, 0) to (i, j).
• Base Cases: Handle destination matching (i == 0 && j == 0) and out-of-bound conditions (return a massive penalty value like 1e9).
• Optimal Substructure: The cost at any cell is grid[i][j] + min(up_path, left_path).
• Memoization Benefit: Reduces exponential time complexity down to $O(N \times M)$.
• Space Optimization Trick: Since row i only depends on row i - 1, we can compress $O(N \times M)$ space down to $O(M)$ using rolling arrays (prev and curr).