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/