LeetCode第64题(动态规划):最小路径和

LeetCode第64题(动态规划):最小路径和

========================

题目如下:

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
64. 最小路径和
给定一个包含非负整数的 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 <= grid[i][j] <= 100

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = (int) grid.size();
int n = (int) grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for (int i=1;i<n;i++) {
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for (int i=1;i<m;i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int i=1;i<m;i++){
for(int j=1;j<n;j++) {
dp[i][j] = min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j]);
}
}
return dp[m-1][n-1];
}
};

复杂度分析

  • 时间复杂度:O(mn)。
  • 空间复杂度:O(mn),其中 m 和 n 分别是网格的行数和列数。创建一个二维数组dp,和网格大小相同。
    空间复杂度可以优化,例如每次只存储上一行的dp 值,则可以将空间复杂度优化到 O(n)。

心得: 这是一道比较经典的动规题,难度偏简单,和第62题有着异曲同工之妙,主要是找到初始条件,找到dp[i][j] = min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j])这么一个关系,如果求最大,则用max。这个解法和官方思路是一样的。

我看到一种别人写的Python解法,思路是一样,代码却是简洁不少,但它的用时和内存都超过C++代码。

1
2
3
4
5
6
7
8
class Solution:
def minPathSum(self, grid):
dp = [float('inf')] * (len(grid[0])+1)
dp[1] = 0
for row in grid:
for idx, num in enumerate(row):
dp[idx + 1] = min(dp[idx], dp[idx + 1]) + num
return dp[-1]

题目链接:https://leetcode-cn.com/problems/minimum-path-sum/