不同路径
Leetcode 62
学习记录自代码随想录文章来源：https://www.toymoban.com/news/detail-839458.html
要点：1.二维表格，想到（i，j）去代表其坐标，dp数组也因此为二维数组；
2.递推公式
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]的上一步只能是其左边或上边，所以
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
+
d
p
[
i
]
[
j
−
1
]
dp[i][j]=dp[i-1][j]+dp[i][j-1]
dp[i][j]=dp[i−1][j]+dp[i][j−1]。文章来源地址https://www.toymoban.com/news/detail-839458.html
class Solution {
public:
int uniquePaths(int m, int n) {
if(m == 1 || n == 1) return 1; // 间接的dp数组初始值
// 1.dp[i][j]，代表从（0，0）到（i，j）有dp[i][j]条路径
vector<vector<int>> dp(m, vector<int>(n, 0));
// int dp[m][n];
// 2.递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 3.初始化：dp[i][0] = 1, dp[0][j] = 1
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int j = 0; j < n; j++) dp[0][j] = 1;
// 4.遍历顺序，从左到右
// 5.举例推导
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];
}
};
到了这里，关于动态规划 Leetcode 62 不同路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
