Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Have you met this question in a real interview?

Yes

Example

Note

You can only move either down or right at any point in time.

public class Solution {

    /**

     * @param grid: a list of lists of integers.

     * @return: An integer, minimizes the sum of all numbers along its path

     */

    public int minPathSum(int[][] grid) {

        // write your code here

        int m = grid.length, n = grid[0].length;

        int[] record = new int[n];

        record[0] = grid[0][0];

        for(int i = 1; i < n; i++){

            record[i] = grid[0][i] + record[i-1];

        }

        for(int i = 1; i < m; i++){

            record[0] += grid[i][0];

            for(int j = 1; j < n; j++){

                record[j] = Math.min(record[j-1], record[j]) + grid[i][j];

            }

        }

        return record[n-1];

        

    }

}