62 不同路径
深搜(超时)
从左上(1,1)开始往下遍历,函数调用图和二叉树非常相似
重复大量无用节点
这棵树的深度其实就是m+n-1(深度按从1开始计算)。
那二叉树的节点个数就是$ 2^(m + n - 1) - 1$。可以理解深搜的算法就是遍历了整个满二叉树(其实没有遍历整个满二叉树,只是近似而已)
所以上面深搜代码的时间复杂度为\(O(2^{m + n - 1} - 1)\),可以看出,这是指数级别的时间复杂度,是非常大的。
class Solution {
private:
int dfs(int i, int j, int m, int n){
if(i > m || j > n) return 0;
if(i == m && j == n) return 1;
return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
}
public:
int uniquePaths(int m, int n) {
return dfs(1, 1, m, n);
}
};
动态规划
两维做法
初始化dp[i][0] = 1和dp[0][j] = 1
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
// 由于机器人每次只能往下或往右
// 所以dp[i][0]和dp[0][j]只有一条路
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int j = 0; j < n; j++) dp[0][j] = 1;
// 从dp[i][j]开始,路径来源可以是dp[i - 1][j]和dp[i][j - 1]
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
时间复杂度:O(m × n)
空间复杂度:O(m × n)
一维优化
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];分析这一递推公式,我们能够发现:在从上到下,从左到右的递归顺序下:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];的效果和dp[j] = dp[j] + dp[j - 1];相同,因为dp[j]保存的就是dp[i - 1][j]的值,dp[j - 1]保存的就是dp[i][j - 1]的值,更新dp[j]之后dp[j]就变成了dp[i][j]
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n, 0);
// 由于机器人每次只能往下或往右
// 所以dp[i][0]和dp[0][j]只有一条路
for(int j = 0; j < n; j++) dp[j] = 1;
// 从dp[i][j]开始,路径来源可以是dp[i - 1][j]和dp[i][j - 1]
for(int i = 1; i < m; i++){
// 这里从j = 0开始或者j = 1开始都可以,因为没有条件能够更改dp[i][0]的状态
for(int j = 1; j < n; j++){
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
};
时间复杂度:O(m × n)
空间复杂度:O(n)
数论做法
一共\(m - 1 + n -1 = n + m -2\)步,选择其中m - 1步往下,得到组合数就是题解:\(C_{n + m - 2}^{m - 1}\)
见https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html#%E6%80%9D%E8%B7%AF