30分钟入门动态规划
共 3779字，需浏览 8分钟
·
2021-09-21 05:00
题目描述
给定一个包含非负整数的 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 <= gridi <= 100
题解
此题是典型的动态规划题目，可以作为入门题，不过要比爬楼梯还要稍微复杂点。
先来了解下概念，所谓动态规划，本质上也是递归，找重复，不过与递归的区别是要把问题分解为最优子问题，所谓最优子问题，是指这个子问题大部分情况下可以代表最佳解题思路。如果你知道分治解法，动态规划与分治法的区别就是，分治是为了分而分，不在乎是否最优，有可能每个子问题之间有重复计算；而动态规划就是找到最优解，一击致命地找到最佳解题方案，把一个复杂问题分解为若干子问题，每个子问题是相互独立的，最后把这些子问题的值合并，得到最终解。
就这个问题来说，要从左上角走到右下角，要找一条路径上的数值和为最小的路。再直白点说，就是从grid[0][0] 走到`grid[m][n]的最小值（m,n表示行列数）。如果用i,j表示行列的指针，那如果可以求得走到grid[i][j]的最小值，就是题解的关键了，那我们就用dp[i][j]来表示走到当前点的最小路径。
那对于grid[i][j]来说，走到当前位置，要么从其上方，要么从其左方，要取这两种路径的最小值，最后再加上此点本身。那么 dp 方程(状态转移方程)就是这样了：
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
上面的考虑还是有漏洞，要考虑i=0或者j=0的情况，也就是当前点在左侧边上或者第一行，这种情况，上面的公式不成立，需要单独列出来：
//在左侧边上即第1列
dp[i][0] = dp[i-1][0]+ grid[i][0];
//在第1行
dp[0][j] = dp[0][j-1]+ grid[0][j-1]
完整代码就是这样：
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
var r = grid.length, c = grid[0].length;
var dp = Array.from(new Array(r),() => new Array(c));
dp[0][0] = grid[0][0];
for (var i = 0; i < r; i++) {
for (var j = 0; j < c; j++) {
// 在第一行
if(i===0&&j!==0)
dp[i][j] = dp[i][j - 1] + grid[i][j];
// 在第一列
else if(i!== 0&& j===0)
dp[i][j] = dp[i-1][j] + grid[i][j];
else if(i!==0&&j!==0)
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[r - 1][c - 1];
};
动态规划题目的套路就是要找到你的状态态转移方程：dp，这个方程是动态规划的灵魂；还有一个要点是这个方程一定要有一个临界值，而且这个值是可以直接出结果的，有了方程和一个常量临界值，就可以依靠计算机的强大计算能力，递推计算出所有情况的值，最后合并为结果。
复杂度分析
时间复杂度：O(mn)
空间复杂度：O(mn)，这个要解释下，因为创建了一个二维数组，所以复杂度是O(mn)
题目链接：https://leetcode-cn.com/problems/minimum-path-sum