64. Minimum Path Sum

Description

Given a m x n grid filled with non-negative numbers, find a path from the top left to the bottom right, which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

Intuition

The problem can be visualized as finding the minimum cost path in a grid where each cell has a non-negative cost. To find the optimal path, one needs to consider the cost of reaching each cell from its possible predecessors (top or left). This suggests a dynamic programming approach where we build up the solution from the smallest subproblems.

Approach

1. Initialization: - Define a 2D list t to store the minimum path sums for each cell, initialized to -1. - Start from the bottom-right corner of the grid and recursively compute the minimum path sum to each cell.
2. Recursive Function: - Base Cases: - If the cell is at the top-left corner, return its value as the minimum path sum. - If the cell indices are out of bounds, return infinity (a very large value). - Memoization: - If the minimum path sum for a cell is already computed (i.e., t[m][n] != -1), return the stored value. - Recursive Calculation: - Compute the minimum path sums for the cell directly above and to the left. - Update the cell's value in t with the minimum of the sums from the top and left plus the cell's own value.
3. Result: - The result for the bottom-right corner of the grid will be the minimum path sum from the top-left to bottom-right.

Complexity

Time Complexity:

O(m * n), where m is the number of rows and n is the number of columns in the grid. Each cell is computed only once and stored.

Space Complexity:

O(m * n) for the memoization table t, plus the recursion stack space which can be up to O(m + n) in the worst case.

Code

C++

class Solution {
public:
    int minPathSum(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector> t(m, vector(n, -1));
        return solve(grid, m - 1, n - 1, t);
    }
private:
    int solve(vector>& arr, int m, int n, vector>& t) {
        if (m == 0 && n == 0) {
            return arr[0][0];
        } else if (m < 0 || n < 0) {
            return INT_MAX;
        }
        if (t[m][n] != -1) {
            return t[m][n];
        }
        int fromTop = solve(arr, m - 1, n, t);
        int fromLeft = solve(arr, m, n - 1, t);
        if (fromTop != INT_MAX) {
            fromTop += arr[m][n];
        }
        if (fromLeft != INT_MAX) {
            fromLeft += arr[m][n];
        }
        t[m][n] = min(fromTop, fromLeft);
        return t[m][n];
    }
};

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        t = [[-1 for _ in range(n)] for _ in range(m)]
        return self.solve(grid, m - 1, n - 1, t)

    def solve(self, arr: List[List[int]], m: int, n: int, t: List[List[int]]) -> int:
        if m == 0 and n == 0:
            return arr[0][0]
        elif m < 0 or n < 0:
            return float("inf")
        if t[m][n] != -1:
            return t[m][n]

        from_top = self.solve(arr, m - 1, n, t)
        from_left = self.solve(arr, m, n - 1, t)

        if from_top != float("inf"):
            from_top += arr[m][n]
        if from_left != float("inf"):
            from_left += arr[m][n]

        t[m][n] = min(from_top, from_left)
        return t[m][n]

Java

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] t = new int[m][n];
        // Initialize the memoization array with -1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                t[i][j] = -1;
            }
        }
        return solve(grid, m - 1, n - 1, t);
    }
    private int solve(int[][] arr, int m, int n, int[][] t) {
        if (m == 0 && n == 0) {
            return arr[0][0];
        } else if (m < 0 || n < 0) {
            return Integer.MAX_VALUE;
        }
        if (t[m][n] != -1) {
            return t[m][n];
        }
        int fromTop = solve(arr, m - 1, n, t);
        int fromLeft = solve(arr, m, n - 1, t);

        if (fromTop != Integer.MAX_VALUE) {
            fromTop += arr[m][n];
        }
        if (fromLeft != Integer.MAX_VALUE) {
            fromLeft += arr[m][n];
        }
        
        t[m][n] = Math.min(fromTop, fromLeft);
        return t[m][n];
    }
}

JavaScript

var minPathSum = function(grid) {
     let m = grid.length,n = grid[0].length
     t = new Array(m+1)
     for (let i = 0;i