leetcode64.最小路径和

题目

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

用例

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

输入：grid = [[1,2,3],[4,5,6]]
输出：12

求解

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    //动态规划
    let m = grid.length
    let n = grid[0].length
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(i==0){
                if(j==0){
                   grid[i][j]=grid[i][j] 
                }else{
                    grid[i][j]=grid[i][j-1]+grid[i][j]
                } 
            }else{
                if(j==0){
                   grid[i][j]=grid[i][j]+grid[i-1][j]
                }else{
                    grid[i][j]=grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1])
                }
            }
        }
    }
    return grid[m-1][n-1]
};