LeetCode偶尔一题 —— 64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:

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

分析题目

递归

对于有些题目,如果我们一下子想不出来解题思路,其实可以稍微对它分析一下,那么自然就会找到解题的办法。
根据题中描述,我们知道每次只能向下或者向右移动一步,我们以此为依据画出示例中所有可能的路径👇

很明显这是一个树形结构,我们只要算出每个头结点叶子结点所经过的路径和,它们中最小的值就是题目中要求的最小路径和,因此我们可以尝试用深度优先搜索来解决它,第一版程序👇

1
2
3
4
5
6
7
8
9
10
11
12
var minPathSum = function (grid) {
return dfs(0, 0)
function dfs (i, j) {
if (i === grid.length || j === grid[0].length) {
return Number.MAX_SAFE_INTEGER
}
if (i === grid.length - 1 && j === grid[0].length - 1) {
return grid[i][j]
}
return grid[i][j] + Math.min(dfs(i + 1, j), dfs(i, j + 1))
}
}

动态规划

细心的你可能已经发现,这道题其实可以把它分解为一个个子问题,而我们只要解决了子问题,那么只要把子问题合并起来就能给出解。
怎么说呢?原题目让我们求到 grid[i][j] 的最小路径,那么我们只要找到 grid[i][j]上一个或者左一个中和它加起来最小的一个。换成代码也就是求👉 min = Math.min(grid[i][j] + grid[i - 1][j], gird[i][j] + grid[i][j-1])

具体实现如下👇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var minPathSum = function(grid) {
let x = grid.length - 1, y = grid[0].length - 1
for (let i = 0; i <= x; i++) {
for (let j = 0; j <= y; j++) {
let tmp = grid[i][j]
if (j === 0) {
if (i > 0) {
grid[i][j] = grid[i - 1][j] + tmp
}
} else {
if (i > 0) {
grid[i][j] = Math.min(grid[i - 1][j] + tmp, grid[i][j - 1] + tmp)
} else {
grid[i][j] = grid[i][j - 1] + tmp
}
}
}
}
return grid[x][y]
};

原题地址: https://leetcode-cn.com/problems/minimum-path-sum/
代码不定时更新,欢迎 star 我的 repo