从m*n矩形左上角走到右下角最短路径有多少种走法,用c++写出代码
时间: 2024-09-11 16:04:26 浏览: 46
对源图像指定区域(通过矩形的左上角和右下角的坐标点指定)使用最小误差最佳阈值法,通过迭代获得该区域的最佳阈值.rar
从一个m*n的矩形左上角走到右下角的最短路径数量,可以通过动态规划来解决。每次只能向下或向右移动一步,因此到达某一点的路径数量等于到达它上方点的路径数量加上到达它左边点的路径数量。
以下是一个使用C++实现的示例代码:
```cpp
#include <iostream>
#include <vector>
int uniquePaths(int m, int n) {
std::vector<std::vector<int>> dp(m, std::vector<int>(n, 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];
}
int main() {
int m = 3; // 矩形的行数
int n = 3; // 矩形的列数
std::cout << "总共有 " << uniquePaths(m, n) << " 种走法。" << std::endl;
return 0;
}
```
在这个代码中,`uniquePaths`函数创建了一个二维数组`dp`,其中`dp[i][j]`表示从左上角走到`(i, j)`位置的路径数量。初始时,第一行和第一列的所有路径数量都设为1,因为只能向右或向下移动。然后,我们遍历矩阵的其余部分,并使用到达上方和左边点的路径数量之和来填充每个点的`dp`值。
阅读全文