算法每日一练-9
算法每日一练 (9)
💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥
官方站点：
算法每日一练 (9)
最小路径和
题目地址：
题目描述
给定一个包含非负整数的
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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
解题思路
首先根据题目要求判断边界条件，当
m == n == 1时，不需要任何处理，直接返回即可。由题意可知，在矩阵中任何一个节点只有一种方式可到达：从左边或上边，那么假设
i是矩阵的横坐标，j是矩阵的纵坐标，则有如下规则：当
i == 0并且j == 0时，就是(0,0)点，到达当前位置的路径最小和满足如下公式：t m p [ i ] [ j ]
g r i d [ i ] [ j ] tmp[i][j] = grid[i][j]
t
m
p
[
i
]
[
j
]
=
g
r
i
d
[
i
]
[
j
]
当
i == 0时，只能从左边到达，到达当前位置的路径最小和满足如下公式：t m p [ i ] [ j ]
g r i d [ i ] [ j ] + t m p [ i ] [ j − 1 ] tmp[i][j] = grid[i][j] + tmp[i][j-1]
t
m
p
[
i
]
[
j
]
=
g
r
i
d
[
i
]
[
j
]
t
m
p
[
i
]
[
j
−
1
]
当
j == 0时， 只能从上面到达，到达当前位置的路径最小和满足如下公式：t m p [ i ] [ j ]
g r i d [ i ] [ j ] + t m p [ i − 1 ] [ j ] tmp[i][j] = grid[i][j] + tmp[i-1][j]
t
m
p
[
i
]
[
j
]
=
g
r
i
d
[
i
]
[
j
]
t
m
p
[
i
−
1
]
[
j
]
当
i != 0并且j != 0时，到达当前位置的路径最小和满足如下公式：t m p [ i ] [ j ]
g r i d [ i ] [ j ] + m i n ( t m p [ i − 1 ] [ j ] , t m p [ i ] [ j − 1 ] ) tmp[i][j] = grid[i][j] + min(tmp[i-1][j], tmp[i][j-1])
t
m
p
[
i
]
[
j
]
=
g
r
i
d
[
i
]
[
j
]
min
(
t
m
p
[
i
−
1
]
[
j
]
,
t
m
p
[
i
]
[
j
−
1
])
- 创建临时矩阵
tmp，根据以上的公式依次给矩阵中的每个元素赋值。 - 返回
tmp[m-1][n-1]的值，因为tmp[m-1][n-1]存储的是就是到达右下角的最小路径和。
golang的解法采用了上述的解题思路；c/c++和lua的解法采用了一维数组作为临时容器，感兴趣的同学可以作为参考。
解题代码
c/c++
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
if (m == 1 && n == 1)
return grid[0][0];
std::vector<int> tmp;
tmp.resize(n);
for (int j = 0; j < n; j++) {
if (j == 0)
tmp[j] = grid[0][j];
else
tmp[j] = grid[0][j] + tmp[j - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0)
tmp[j] += grid[i][j];
else
tmp[j] = grid[i][j] + std::min(tmp[j - 1], tmp[j]);
}
}
return tmp[n - 1];
}
};golang
func minPathSum(grid [][]int) int {
m := len(grid)
n := len(grid[0])
if m == 1 && n == 1 {
return grid[0][0]
}
tmp := make([][]int, m)
for i := 0; i < m; i++ {
tmp[i] = make([]int, n)
for j := 0; j < n; j++ {
if i == 0 && j == 0 {
tmp[i][j] = grid[i][j]
} else if i == 0 {
tmp[i][j] = grid[i][j] + tmp[i][j-1]
} else if j == 0 {
tmp[i][j] = grid[i][j] + tmp[i-1][j]
} else {
tmp[i][j] = grid[i][j] + min(tmp[i-1][j], tmp[i][j-1])
}
}
}
return tmp[m-1][n-1]
}lua
local function minPathSum(grid)
local m, n = #grid, #grid[1]
if m == 1 and n == 1 then
return grid[1][1]
end
local tmp = {}
for j = 1, n do
if j == 1 then
tmp[j] = grid[1][j]
else
tmp[j] = grid[1][j] + tmp[j - 1]
end
end
for i = 2, m do
for j = 1, n do
if j == 1 then
tmp[j] = tmp[j] + grid[i][j]
else
tmp[j] = grid[i][j] + math.min(tmp[j], tmp[j - 1])
end
end
end
return tmp[n]
end🌺🌺🌺撒花！
如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。
