Accepted DP Solution, Java, O(N) space


  • 0
    W

    For each entry of the matrix, the min sum is : current number + Math.min(sum of left entry, sum of top entry),
    that is, minSum[x][y] = grid[x][y] + Math.min(minSum[x-1][y], minSum[x][y-1]).

    Actually we can present minSum[x][y-1] just use minSum[x][y] before we do the sum. So the space for one row is enough.

    /**
     *   DP
     **/
    public class Solution {
        public int minPathSum(int[][] grid) {
            
            int cols=grid[0].length; // get row length
            int rows=grid.length; // get row number
            
            int[] dp = new int[cols];
            dp[0] = grid[0][0]; // init state
            
            for(int i=0; i<rows; ++i){
                for(int j=0; j<cols; ++j){
                    if(i==0){
                        if(j>0){
                            dp[j] = grid[i][j] + dp[j-1];
                        }
                        
                    }else{
                        if(j>0){
                            dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);
                        }else{
                            dp[j] = grid[i][j] + dp[j];
                        }
                    }
                }
            }
            
            return dp[cols-1];
        }
        
    }

Log in to reply
 

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