Minimum Path Sum最小路径和（动态规划）

leetcode 64

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.

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

Example 1:

[[1,3,1],
 [1,5,1],
 [4,2,1]]

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

思路

跟unique path一样，这个不用设置数组dp来记录，只需要更改grid即可，每次把加起来的更小的数存下

var minPathSum = function(grid) {
    var m=grid.length;
    var n=grid[0].length;
    for(var i=0;i<m;i++){
        for(var j=0;j<n;j++){
            if(i===0 && j>0){
                grid[i][j]+=grid[0][j-1];
            }else if(j===0 && i>0){
                grid[i][j]+=grid[i-1][j];
            }else if(i>0 && j>0){
                grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1])
            }
        }
    }
    return grid[m-1][n-1];
};