欢迎访问LeetCode题解合集
题目描述
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例1:
输入:m = 3, n = 7
输出:28
示例2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例3:
输入:m = 7, n = 3
输出:28
示例4:
输入:m = 3, n = 3
输出:6
提示:
- $1 \le m, n \le 100$
- 题目数据保证答案小于等于 $2 * 10^9$
题解:
动态规划。
设 f[i][j]
表示从 (0,0)
到 (i,j)
的不同路径数目,题目中说明了机器人每次只能向下或者向右移动一步,可以得到状态转移方程:
f[i][j] = f[i - 1][j] + f[i][j - 1]
,即每个位置只跟左边和上方有关。
注意,第一行和第一列都初始化为 1
,因为只能沿着一个方向走。
时间复杂度:$O(m*n)$
额外空间复杂度:$O(m * n)$
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f( m, vector<int>(n, 0) );
for ( int i = 0; i < n; ++i ) f[0][i] = 1;
for ( int i = 1; i < m; ++i ) f[i][0] = 1;
for ( int i = 1; i < m; ++i ) {
for ( int j = 1; j < n; ++j ) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
};
/*
时间:0ms,击败:100.00%
内存:6.3MB,击败:60.37%
*/
可以发现,f[i][j]
只跟 f[i-1][...]
和 f[i][...]
有关,可以使用滚动数组优化掉第一维。
时间复杂度:$O(m*n)$
额外空间复杂度:$O(n)$
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> f(n);
f[0] = 1;
for ( int i = 0; i < m; ++i ) {
for ( int j = 0; j < n; ++j ) {
if ( j ) f[j] += f[j - 1];
}
}
return f[n - 1];
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:99.15%
*/