java solution (DP) with no extra space and time O(n)


  • 0
    5

    public class Solution {
    public int minPathSum(int[][] grid) {
    if(grid==null){
    return 0;
    }
    int m=grid.length;
    int n=grid[0].length;

        for(int i=1;i<m;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int j=1;j<n;j++){
            grid[0][j]+=grid[0][j-1];
        }
        
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]=Math.min(grid[i][j-1],grid[i-1][j])+grid[i][j];
            }
        }
        return grid[m-1][n-1];
    }
    

    }


Log in to reply
 

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