给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：一个机器人每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
注意：本题与主站 64 题相同：
https://leetcode-cn.com/problems/minimum-path-sum/看完题目之后没多想误认为是走迷宫的题，于是写了一版暴力 DFS ，结果超时了。代码逻辑是从左上角到右下角进行深度遍历，并且累计路径和代入下一步计算。
超时的原因在于 ：通常走迷宫的题不会重复经过某个节点，因此时间复杂度是 O(mn)，以 m,n<=200 来算不会超时； 但这个题目的暴力 DFS 可以看做是遍历一棵高度为 n+m−1 的二叉树，时间复杂度接近指数级的 2n+m−1，超时也不足为奇。
从网格左上角到右下角的最短路径长度为 n+m−1，因此把它当成树的话高度为 n+m−1
暴力DFS超时代码
var minPathSum = function (grid) {
const m = grid.length, n = grid[0].length
let min = Infinity;
function dfs(i, j, sum) {
if (i >= m || j >= n) return;
sum += grid[i][j]
if (i === m - 1 && j === n - 1) min = Math.min(min, sum);
dfs(i + 1, j, sum);
dfs(i, j + 1, sum);
}
dfs(0, 0, 0);
return min;
};
通常暴力 DFS 可以通过剪枝、记忆化等方式进行优化，这里采用了剪枝优化，优化后AC了但耗时 3208 ms 依然很高。
这里的问题在于：
- 上述DFS代码属于暴力遍历所有情况并在终点时计算最小值，没有求局部最优解的倾向
- 剪枝优化不稳定：这里剪枝的方式是记录节点前序路径和，当再次访问该节点时判断当前情况的前序路径和是否更小，以决定是否继续遍历以及是否更新该前序路径和，这种剪枝方式存在不稳定性，因为记录的前序路径和不是最小，后续遍历可能会有更小的前序路径和出现，所以这种剪枝没办法排除掉最小值以外的所有情况
var minPathSum = function (grid) {
const m = grid.length, n = grid[0].length
let min = Infinity, minPreSum = new Map();
function dfs(i, j, sum) {
const key = i + '-' + j;
if (i >= m || j >= n || sum >= (minPreSum.get(key) || Infinity)) return;
minPreSum.set(key, sum);
sum += grid[i][j]
if (i === m - 1 && j === n - 1) min = Math.min(min, sum);
dfs(i + 1, j, sum);
dfs(i, j + 1, sum);
}
dfs(0, 0, 0);
return min;
};
这个解法思路接近于动态规划， dfs 函数的意图是求局部最优解最终得到全局最优解，其中 dfs(i, j) 代表从终点 (m, n) 到点 (i, j) 的最小路径和，然后通过哈希表记录点 (i, j) 的最小路径和，后续再次遍历到该节点直接返回最小路径和，无需多余遍历与计算。
var minPathSum = function (grid) {
const m = grid.length, n = grid[0].length
const minSum = new Map();
function dfs(i, j) {
if (i >= m || j >= n) return Infinity;
if (i === m - 1 && j === n - 1) return grid[i][j];
const key = i + '-' + j;
if (minSum.has(key)) return minSum.get(key);
const min = Math.min(dfs(i + 1, j), dfs(i, j + 1)) + grid[i][j];
return minSum.set(key, min), min;
}
return dfs(0, 0);
};
解法2采用的是逆序累加和求解，这里为了方便理解采用顺序累加和进行求解。从题意可以看出对于任意节点 (i, j)，其最小路径和取决于上方节点 (i-1, j) 和左方节点 (i, j-1)，其值为左上两个节点中最小路径和的较小值加上自身的值。
dp 数组含义：dp 数组是一个 (m+1)*(n+1) 的数组，其中 dp[i][j] 表示从起点 (0, 0) 到点 (i, j) 的最小路径和，其中第一行和第一列只是为了方便计算，没有实际含义- 状态转移方程是：
i === 1 && j === 1 时：dp[i][j] = grid[i - 1][j - 1]- 其他情况：
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
dp[i][j] 对应的节点是 grid[i - 1][j - 1]，因此遍历 dp 数组时 i 和 j 都从下标 1 开始
var minPathSum = function (grid) {
const m = grid.length, n = grid[0].length
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(Infinity));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (i === 1 && j === 1) dp[i][j] = grid[i - 1][j - 1];
else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
}
}
return dp[m][n];
};
题解区有更优秀的动态规划解法，有降维 DP（一维）、有把原始数组 grid 作为 DP 数组等，主要降低了空间复杂度，很值得学习。
