题目
给定一个包含非负整数的 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.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
1、设置状态。
令dp[i][j]表示走到(i,j)点的最小路径和。
2、状态转移方程。
如何求出dp[i][j]？
由于每次只能往右走或者下走。换言之，当前单元格dp[i][j]的前继状态只有dp[i-1][j],dp[i][j-1]，所以我们在两者取最小，然后加上当前格子内的数即可。
走到当前单元格(i,j)的最小路径和 = 【从左方单元格 (i-1,j) 与 从上方单元格 (i,j−1) 走来的 两个最小路径和中较小的】 + 当前单元格值 grid[i][j]
dp(i,j) = grid(i,j) + min(dp(i-1,j),dp(i,j-1))
具体分以下4种情况:
- 当左边和上边都不是矩阵边界时：即
i!=0, j!=0
dp(i,j) = grid(i,j) + min(dp(i-1,j),dp(i,j-1))
- 当只有左边是矩阵边界时：只能从上面来，即
i=0,j!=0
dp(i,j) = grid(i,j) + dp(i,j-1)
- 当只有上边是矩阵边界时：只能从左面来，即
i!=0,j=0
dp(i,j) = grid(i,j) + dp(i-1,j)
- 当左边和上边都是矩阵边界时：即
i=0,j=0，其实就是起点
dp(i,j) = grid(i,j)
作者：jyd 链接：https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
JS实现
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function (grid) {
if (grid === null || grid.length === 0 || grid[0].length === 0) {
return 0;
}
const rows = grid.length,
columns = grid[0].length;
// 创建二维dp数组
// dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和
const dp = Array.from({ length: rows }, (x) =>
Array.from({ length: columns })
);
dp[0][0] = grid[0][0];
for (let i = 0; i < rows; i++) {
for (let j = 0; j < columns; j++) {
if (i === 0 && j === 0) {
dp[i][j] = grid[i][j];
} else if (i === 0 && j != 0) {
dp[i][j] = grid[i][j] + dp[i][j - 1];
} else if (i != 0 && j === 0) {
dp[i][j] = grid[i][j] + dp[i - 1][j];
} else if (i != 0 && j != 0) {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[rows - 1][columns - 1];
};