dp O(mn) time O(mn) space
需要注意边界条件
f[0][0] = grid[0][0]
f[0][j] = f[0][j - 1] + grid[0][j]
f[i][0] = f[i - 1][0] + grid[i][0]
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size();
vector<vector<int>> f(m + 1, vector<int>(n + 1, INT_MAX));
f[1][0] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
}
}
return f[m][n];
}
};
|
O(mn) time O(n) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size();
vector<int> f(n + 1, INT_MAX);
f[0] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
f[j] = min(f[j], f[j - 1]) + grid[i - 1][j - 1];
}
f[0] = INT_MAX;
}
return f[n];
}
};
|