DP solution with explanation (beating 93% java solutions)


  • 0
    E

    Analysis: The path has to start from upper left corner and end at lower right corner. Therefore, it is easy to show by contradictory that for an optimum path will always go in the right or down directions, but never in up or left direction.

    The idea is then quite straightforward: for a given column, we store the shortest path from the upper left corner to any row in that column in an array.

    Java code is as follows:

    public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        if(m<1) return 0;
        
        int n = grid[0].length;
        
        int[] dp = new int[m];
        dp[0] = grid[0][0];
        for(int i=1; i<m; i++) dp[i] = dp[i-1] + grid[i][0]; // dp[1] is the shortest path from grid[0][0] to grid[1][0].
            
        for(int i=1; i<=n-1; i++) {
            dp[0] = dp[0] + grid[0][i];
            for(int j=1; j<m; j++)
                dp[j] = (dp[j] < dp[j-1] ? dp[j] : dp[j-1]) + grid[j][i]; // dp[j] is the shortest path from grid[0][0] to grid[j][i]
        }
        return dp[m-1]; // only dp[m-1] ends at lower right corner
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.