Short java solution dp with O(n) space


  • -2
    J
    public int minPathSum(int[][] grid) {
        if(grid.length==0)  return 0;
        int[] dp = new int[grid[0].length+1];
        for(int i=grid.length-1;i>=0;i--)
            for(int j=grid[0].length-1;j>=0;j--)    
                dp[j] = grid[i][j] + Math.min((i==grid.length-1)?Integer.MAX_VALUE:dp[j],(j==grid[0].length-1&&i!=grid.length-1)?Integer.MAX_VALUE:dp[j+1]);
        return dp[0];
    }
    

    Another solution which is easy to understand.

    public int minPathSum(int[][] grid){
        if(grid.length == 0)    return 0;
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n+1];
        for(int i = n - 2; i >= 0; i--) dp[i] = dp[i+1] + grid[m-1][i+1];
        for(int i = m - 1; i >= 0; i--){
            if(i < m - 1)    dp[n] = dp[n-1];
            for(int j = n - 1; j >= 0; j--)
                dp[j] = Math.min(dp[j], dp[j+1]) + grid[i][j];
        }
        return dp[0];
    }

  • 0
    S

    where the values of dp calculated and assigned?


  • 0
    J

    at right most


  • 0
    T

    I usually define "code length" by "time to understand this piece of code", yours is extremely long...


Log in to reply
 

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