64\. 最小路径和
# 64. 最小路径和 (opens new window)
# Description
Difficulty: 中等
Related Topics: 数组 (opens new window), 动态规划 (opens new window), 矩阵 (opens new window)
给定一个包含非负整数的 _m_ x _n_
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
**说明:**每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
1
2
3
2
3
示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
1
2
2
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
# Solution
Language: JavaScript
/**
* @param {number[][]} grid
* @return {number}
* 方法一:动态规划
* 1. 状态的设置
* 在这个题目里,由于要求最小路径和,我们可以令
* dp[i][j]代表从(i, j)点走到(m-1, n-1)点的最小路径和。
* 2. 状态转移方程
* 我们考虑如何求出dp[i][j]。
* 由于每次只能往右或者下走,所以从(i, j)只能走到(i+1, j)或者(i, j+1)。
* dp[i][j]的前继承状态只有dp[i+1][j],dp[i][j+1],所以我们在两者取最小,然后加上这个格子内的数即可。
* dp(i,j) = grid(i,j)+min(dp(i+1, j), dp(i, j+1))
*/
// m列 n行
var minPathSum = function(grid) {
if (grid == null || grid.length == 0 || grid[0].length === 0) {
return 0
}
let row = grid.length, col = grid[0].length
const dp = new Array(row).fill(0).map(() => new Array(col).fill(0))
dp[0][0] = grid[0][0]
for (let i = 1; i < row; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for (let j = 1; j < col; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
for (let i = 1; i < row; i++) {
for (let j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
}
}
return dp[row-1][col-1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41