3ms java dp solution


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

Log in to reply
 

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