原题地址：最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
动态规划
设置一个二维数组，用来记录每个格子到右下角的路径之和。然后从右下角开始扫描，当前格子的最小路径和就等于右边一格的路径和与下方一格路径和中较小的一个与当前格子的路径之和。
具体的实现代码如下：
/**
* @param {number[][]} grid
* @return {number}
*/
const minPathSum1 = function(grid) {
let [m, n] = [grid[0].length, grid.length];
// 路径上一定有当前格子本身，所以初始值为grid数组
let dp = [...grid];
for (let i = n - 1; i >= 0; i --) {
for (let j = m - 1; j >= 0; j --) {
if (i < n - 1 && j < m - 1) {
// 下方和右方都有格子，选择路径较小的一个
dp[i][j] += Math.min(dp[i + 1][j], dp[i][j + 1]);
} else if (i < n - 1) {
// 只有下方还有格子
dp[i][j] += dp[i + 1][j]
} else if (j < m - 1) {
// 只有右边有格子
dp[i][j] += dp[i][j + 1]
}
}
}
// 返回左上角的最小路径和
return dp[0][0]
};
测试：
let start = new Date();
const test = minPathSum1;
console.log(test([
[1,3,1],
[1,5,1],
[4,2,1]
])); // 7
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 需要求解每个格子的最小路径和，时间复杂度为$O(MN)$
空间复杂度： 需要一个额外的$dp$数组来存储每个格子的最小路径和，空间复杂度为$O(MN)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 18,2019