欢迎访问LeetCode题解合集
题目描述
给定一个包含非负整数的 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 \le m, n \le 200$
-
$0 \le grid[i][j] \le 100$
题解:
动态规划。
f[i][j]
表示从 (0,0)
走到 (i,j)
路径上的数字最小和,转移方程为:f[i][j] = min{f[i - 1][j], f[i][j - 1]} + grid[i][j]
注意特殊处理第一行和第一列。
时间复杂度:$O(n*m)$
额外空间复杂度:有三种写法:
写法一:
额外空间复杂度:$O(1)$
直接把 grid
数组当做 f
,在上面更新,算是耍赖了哈哈哈哈。
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 && j )
grid[i][j] += min( grid[i - 1][j], grid[i][j - 1] );
else if ( i ) grid[i][j] += grid[i - 1][j];
else if ( j ) grid[i][j] += grid[i][j - 1];
}
}
return grid[n - 1][m - 1];
}
};
/*
时间:8ms,击败:98.15%
内存:9.3MB,击败:99.22%
*/
写法二:
额外空间复杂度:$O(n*m)$
正儿八经的开辟一个二维数组 f
,计算过程和 写法一 一致。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> f( n, vector<int>(m) );
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < m; ++j ) {
f[i][j] = grid[i][j];
if ( i && j ) f[i][j] += min( f[i - 1][j], f[i][j - 1] );
else if ( i ) f[i][j] += f[i - 1][j];
else if ( j ) f[i][j] += f[i][j - 1];
}
}
return f[n - 1][m - 1];
}
};
/*
时间:12ms,击败:93.80%
内存:9.7MB,击败:92.90%
*/
写法三:
写法二 中,f[i][j]
只跟 f[i][...]
和 f[i-1][...]
有关,可使用滚动数组优化。
额外空间复杂度:$O(m)$
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<int> f(m);
int pre;
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < m; ++j ) {
pre = f[j];
f[j] = grid[i][j];
if ( i && j ) f[j] += min( pre, f[j - 1] );
else if ( i ) f[j] += pre;
else if ( j ) f[j] += f[j - 1];
}
}
return f[m - 1];
}
};
/*
时间:8ms,击败:98.15%
内存:9.4MB,击败:97.16%
*/