Description
Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
1
2
3
4
5
6
7
8
| Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
|
每个格子的数字表示经过它所需的消耗大小。寻找从左上到右下的最少路径消耗。
Solution
似曾相识
本题与《63. Unique Paths II》
使用相同的方法：
要到达右下角，需要经过左边或者上边的格子，而最少消耗自然是从这两个格子中选择到达它们所需消耗（非它们自身消耗）较少的一个：
$$ f(x, y) = cost_{(x,y)} + min(f(x-1, y), f(x, y-1)) $$所以与之前一样，从左上开始往右下分别计算出每个格子的最少消耗，直到最终格子。
Code Here
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
42
43
44
| func minPathSum(grid [][]int) int {
row := len(grid)
if row == 0 {
return 0
}
col := len(grid[0])
if col == 0 {
return 0
}
var left, up, minCost, upCost int
// 从第二个格子开始
j := 1
for i := 0; i < row; i++ {
for ; j < col; j++ {
minCost = -1
left = j - 1
if left >= 0 {
// 左边消耗
minCost = grid[i][left]
}
up = i - 1
if up >= 0 {
// 上边消耗
upCost = grid[up][j]
if upCost < minCost || minCost == -1 {
minCost = upCost
}
}
// 选择较少消耗的路径并加上自身消耗
// 保存当前格子消耗
grid[i][j] += minCost
}
j = 0
}
// 返回最后一个格子消耗
return grid[row-1][col-1]
}
|
Similar Problem