Minimum Path Sum 110

Question

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.

Notice

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

Solution

这题是机器人从左上走到右下的最小path的变体。

pathSum[i][j]表示从（0,0）到（i,j）的最小path。

初始化：

pathSum[i][0]=grid[i][0]+pathSum[i-1][0]
pathSum[0][j]=grid[0][j]+pathSum[0][j-1]

即初始化第一行和第一列

状态函数：

pathSum[i][j] = grid[i][j]+min(pathSum[i][j-1], pathSum[i-1][j])

即从（0，0）到（i，j）的最小path为从（0，0）到其左边格子和上面格子的最小path的较小者＋（i，j）的值。

代码如下：

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
        if(grid == null || grid.length == 0){
            return 0;
        }

        if(grid[0] == null || grid[0].length == 0){
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int[][] pathSum = new int[m][n];
        pathSum[0][0] = grid[0][0];

        for(int i = 1; i < m; i++){
            pathSum[i][0] = pathSum[i - 1][0] + grid[i][0];
        }

        for(int j = 1; j < n; j++){
            pathSum[0][j] = pathSum[0][j - 1] + grid[0][j];
        }

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

        return pathSum[m - 1][n - 1];
    }
}