O(n) space DP solution in java


  • 0
    public int minPathSum(int[][] grid) {
        if(grid==null||grid.length==0||grid[0].length==0)
            return 0;
        int n = grid[0].length;
        int m = grid.length;
        //dp[i] means for each row, the minimum sum for column i+1
        int[] dp = new int[n];
       // initialize dp[]
        dp[0] = grid[0][0];
        for(int i =1;i<n;i++){
            dp[i] = dp[i-1]+grid[0][i];
        }
        for(int j=1;j<m;j++){
            dp[0] = dp[0]+grid[j][0];
            for(int i =1;i<n;i++){
                dp[i] = Math.min(dp[i],dp[i-1])+grid[j][i];
            }
        }
        return dp[n-1];
    }

Log in to reply
 

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