Leetcode: Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Understand the problem:
The problem asks for find the minimum path sum, which is still close to the Unique Path I and II. Note that the grid is filled with non-negative numbers. 

Naive Solution:
The native solution is to use recursion. We get all possible unique paths and get the sum of the path. We only need to maintain the minimum path sum. 

Code (Java):

public class Solution {
    private int min = Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        minPathSumHelper(0, 0, m, n, 0, grid);
        
        return min;
    }
    
    private void minPathSumHelper(int r, int c, int m, int n, int curSum, int[][] grid) {
        if (r > m - 1 || c > n - 1) {
            return;
        }
        curSum += grid[r][c];
        
        if (r == m - 1 && c == n - 1) {
            if (curSum < min) {
                min = curSum;
            }
            return;
        }
        
        if (curSum > min) {
            return;
        }
        
        minPathSumHelper(r + 1, c, m, n, curSum, grid);
        minPathSumHelper(r, c + 1, m, n, curSum, grid);
    }
}

Discussion:
No surprise the solution got the TLE error, since its time complexity is at the order of exponential.  So we must naturally think of a DP solution.

An iterative-based DP solution:

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] dp = new int[m][n];
        
        dp[0][0] = grid[0][0];;
        
        // update the first row
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        
        // update the first column
        for (int j = 1; j < m; j++) {
            dp[j][0] = dp[j - 1][0] + grid[j][0];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

One-dimensional DP Solution:
Again, we can optimize the space by using an 1D DP solution. So dp[i] means the minimum path sum from starting to column i. 

Code (Java):

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        
        // set the first row
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
        
        for (int i = 1; i < m; i++) {
            dp[0] = dp[0] + grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        
        return dp[n - 1];
    }
}

Summary:
The path sum I, II, minimum path sum are a set of very classic DP problem. Try to understand the native recursive solution first. Then think about recursive-based DP, 2D DP and 1D DP solution.


Update on 4/2/19: rolling array

public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[2][n];
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            dp[0][i] = sum + grid[0][i];
            sum += grid[0][i];
        }
        
        int old = 0;
        int cur = 0;
        for (int i = 1; i < m; i++) {
            old = cur;
            cur = 1 - cur;
            dp[cur][0] = dp[old][0] + grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[cur][j] = Math.min(dp[old][j], dp[cur][j - 1]) + grid[i][j];
            }
        }
        
        return dp[cur][n - 1];
    }
}