题目

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

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

示例:

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

思路

这道题是一道经典的动态规范题，我们只要计算二维数组上每个元素的最小数字和即可，

1. 对比上方和左方格子里的值谁小，加上它并替换
2. 如果在上边界或左边界，直接加
3. 一直到右下角，得到值
   结束

代码

以下：
代码

/**
 * @param {number[][]} grid
 * @return {number}
**/
var minPathSum = function(grid) {
    let n = grid.length; // 拿到行数
    let m = grid[0].length // 拿到列数
    // 行循环
    for(let i = 0;i<n;i++) {
	// 列循环
        for(let j = 0; j< m;j++) {
	    // 如果在起点
            if(i == 0 && j==0) {
                grid[i][j] = grid[i][j]
            } else if(i == 0) { // 如果在上边界
		// 直接加上左方的值
                grid[i][j] = grid[i][j] + grid[i][j-1]
            } else if(j == 0) { // 如果在左边界
		// 直接加上上方的值
                grid[i][j] = grid[i][j] + grid[i-1][j]
            } else {
		// 取上方和左方中小的值
		grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]) 
            }
        }
    }
    return grid[n-1][m-1]
};

结束

Q.E.D.