62. 不同路径
3 min
题目
解法：动态规划
思路
动态规划：到达每个格子的路径数等于从上方和左方到达的路径数之和。
该方法正确性基于数学归纳法：基础情况是第一行和第一列只有1条路径；递推关系成立是因为机器人只能从上方或左方到达当前格子，因此总路径数是这两个方向路径数的和。通过填充DP表，每个格子的值都正确表示了到达该位置的路径总数。
- Step 1: 初始化 m×n 的 DP 数组，所有元素为 0
- Step 2: 设置第一行和第一列的所有值为 1
- Step 3: 从 i=1 到 m-1，j=1 到 n-1 遍历
- Step 4: dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Step 5: 返回 dp[m-1][n-1]
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int i = 0; i < n; i++) dp[0][i] = 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];
}
};