LeetCode64. Minimum Path Sum（动态规划）
- Medium
- Accepted：215,048
- Submissions：468,498
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:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.链接
https://leetcode.com/problems/minimum-path-sum
题意
给定一个m * n的网格，其中均为非负整数，找到一条从左上角到右下角的路径，满足路径上的数字和最小，每次可以向右或向下移动。
题解
考虑一下我们之前做的三角形的路径最小值：LeetCode120. Triangle（动态规划），有些类似。
根据题目规则，每次可以向右或向下移动，也就是对于当前的数字，可以从它上边的数字和它左边的数字走到它。
假设$dp[i][j]$表示从左上角走到第i列第j行时路径的最小和，那么递推方程为：$dp[i][j] = dp[i-1][j] + dp[i][j-1]+dp[i][j]$。
注意边界条件，当 i = 0 或 j = 0时，数组下标会超范围，所以需要单独判断，或者在递推之前做个预处理，然后i和j都从1开始。
平均时间复杂度$O(nm)$，在改变原数组的情况下额外空间为$O(1)$。
代码
- Runtime: 12 ms, faster than 99.16% of C++ online submissions for Minimum Path Sum.
- Memory Usage: 10.9 MB, less than 79.87% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (i == 0 && j == 0)
grid[i][j] = grid[i][j];
else if (i == 0 && j != 0)
grid[i][j] = grid[i][j - 1] + grid[i][j];
else if (i != 0 && j == 0)
grid[i][j] = grid[i - 1][j] + grid[i][j];
else
grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
}
}
return grid[n - 1][m - 1];
}
};- Runtime: 12 ms, faster than 99.16% of C++ online submissions for Minimum Path Sum.
- Memory Usage: 10.7 MB, less than 98.11% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
for (int i = 1; i < n; ++i)
grid[i][0] = grid[i - 1][0] + grid[i][0];
for (int j = 1; j < m; ++j)
grid[0][j] = grid[0][j - 1] + grid[0][j];
for (int i = 1; i < n; ++i)
for (int j = 1; j < m; ++j)
grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
return grid[n - 1][m - 1];
}
};事实上我这种写法“不规范”，因为我是在原数组上直接操作的，改变了原数组的值，我们应该再开一个新的二维数组，但是这样的话空间复杂度就会是$O(nm)$，实际上$dp[i][j]$，只它左边的数$dp[i][j-1]$（左列）和上边的数$dp[i-1][j]$（当前列）相关，所以我们只需要用一个数组来维护。
比如我们按行来进行遍历，那么我们需要一个数组cur保存当前行的最左边1个数和上边一行n-1个数的信息。对于样例，$cur[0]_{1, 0} = 1+1 = 2$（处理边界），$cur[1]_{0, 1} = 3 + 1 = 4$，$cur[2]_{0, 2} = 1 + 4 = 5$。然后开始更新，$cur[1]_{1, 1} = max(cur[0]_{1, 0}, cur[1]_{0, 1}) + grid[1][1]$，"5"由左“1”和上“3”更新，具体参考代码。
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]- Runtime: 16 ms, faster than 23.50% of C++ online submissions for Minimum Path Sum.
- Memory Usage: 10.8 MB, less than 94.65% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector <int> cur(m, grid[0][0]);
for (int i = 1; i < m; ++i)
cur[i] = cur[i - 1] + grid[0][i];
for (int i = 1; i < n; ++i)
{
cur[0] += grid[i][0];
for (int j = 1; j < m; ++j)
cur[j] = min(cur[j - 1], cur[j]) + grid[i][j];
}
return cur[m - 1];
}
};参考
The end.
2019年3月24日 星期日