text
function solve(i, j):
    if i or j is out of bounds:
        return infinity
    if i is last row and j is last col:
        return grid[i][j]
    
    move_right = solve(i, j + 1)
    move_down = solve(i + 1, j)
    
    return grid[i][j] + min(move_right, move_down)

Complexity Analysis

The time complexity of this approach is O(2^(m+n)). Because each cell generates two recursive branches, and the path length is m + n, the recursion tree grows exponentially.

Why it fails

This approach fails due to overlapping subproblems. The algorithm re-calculates the minimum path for the same cells millions of times. For a grid of size $200 \times 200$, the number of operations exceeds the computational limits, resulting in a Time Limit Exceeded (TLE) error.

Core Insight for Minimum Path Sum

The key intuition for solving LeetCode 64 efficiently lies in the direction of movement. Since we can only move down or right, a cell at position (i, j) can only be reached from:

1. The cell directly above it: (i-1, j)
2. The cell directly to the left of it: (i, j-1)

This implies that the minimum path sum to reach (i, j) is the value in grid[i][j] plus the smaller of the two cumulative sums calculated for (i-1, j) and (i, j-1).

This creates a recurrence relation: $dp[i][j] = grid[i][j] + \min(dp[i-1][j], dp[i][j-1])$

By solving this iteratively starting from (0, 0), we build a table where every entry represents the global minimum cost to reach that specific coordinate. This eliminates redundant calculations found in the brute force method.

Visual Description: Imagine the grid being filled cell by cell, row by row.

• The top-left cell remains unchanged.
• The cells in the first row can only be reached from the left, so their values become cumulative sums of the row.
• The cells in the first column can only be reached from above, so their values become cumulative sums of the column.
• For all inner cells, the algorithm looks at the computed values directly above and to the left, picks the minimum, adds the current cell's value, and stores the result.

Algorithm Strategy: DP - 2D Array (Unique Paths on Grid)

The strategy employs an iterative bottom-up Dynamic Programming approach. We can either use a separate dp table of the same dimensions as the grid or, to save space, modify the input grid in-place.

1. Initialization: The starting cell (0, 0) is the base cost.
2. Boundary Handling:
   • First Row: Iterate through the first row. Each cell (0, j) is updated to grid[0][j] + grid[0][j-1]. This is because the only way to reach a cell in the first row is from the left.
   • First Column: Iterate through the first column. Each cell (i, 0) is updated to grid[i][0] + grid[i-1][0]. This is because the only way to reach a cell in the first column is from above.
3. Core Iteration: Iterate through the remaining cells starting from (1, 1) to (m-1, n-1).
4. State Transition: For each cell (i, j), update its value to be the current value plus the minimum of the value above it and the value to its left.
5. Result: The value at the bottom-right corner (m-1, n-1) will contain the minimum path sum.

Execution Flow

1. Setup: Check if the grid is empty. If so, return 0. Get dimensions m (rows) and n (cols).
2. Process First Row: Loop from j = 1 to n-1. Update grid[0][j] += grid[0][j-1].
3. Process First Column: Loop from i = 1 to m-1. Update grid[i][0] += grid[i-1][0].
4. Process Inner Grid:
   • Outer loop i from 1 to m-1.
   • Inner loop j from 1 to n-1.
   • Calculate min_prev = min(grid[i-1][j], grid[i][j-1]).
   • Update grid[i][j] += min_prev.
5. Return: Return grid[m-1][n-1].

Proof of Correctness

The correctness relies on the Principle of Optimality.

• Base Case: The path to (0,0) is trivially correct (cost is grid[0][0]).
• Inductive Step: Assume that for any cell (x, y) where x < i or y < j, the algorithm has correctly computed the minimum path sum. To compute the optimal path to (i, j), the path must arrive from either (i-1, j) or (i, j-1). Since grid[i][j] is non-negative and we select the minimum of the two optimal predecessors, the sum at (i, j) is guaranteed to be minimal.
• Conclusion: Since we iterate in topological order (top-left to bottom-right), dependencies are always resolved before use, ensuring the final value at (m-1, n-1) is the global minimum.

Reference Implementation

C++ Solution for LeetCode 64

cpp
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int m = grid.size();
        int n = grid[0].size();
        
        // Initialize first row (can only come from left)
        for (int j = 1; j < n; ++j) {
            grid[0][j] += grid[0][j - 1];
        }
        
        // Initialize first column (can only come from up)
        for (int i = 1; i < m; ++i) {
            grid[i][0] += grid[i - 1][0];
        }
        
        // Fill the rest of the grid
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                // Current cell cost + min(top, left)
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
};

Java Solution for LeetCode 64

java
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int m = grid.length;
        int n = grid[0].length;
        
        // Initialize first row (accumulate sums from left)
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        
        // Initialize first column (accumulate sums from top)
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        
        // Process the inner cells
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // The cost is current value + min of top or left neighbor
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
}

Python Solution for LeetCode 64

python
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
            
        m, n = len(grid), len(grid[0])
        
        # Initialize first row (accumulate sums from left)
        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]
            
        # Initialize first column (accumulate sums from top)
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
            
        # Process the inner cells
        for i in range(1, m):
            for j in range(1, n):
                # Update current cell with min path from top or left
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
                
        return grid[m - 1][n - 1]