用c++完成这道题:有一个 n \times mn×m 的矩阵迷宫,每个点都可以走,如果从 1,11,1 点出发,只能向下或者向右行走,请问走到 n,mn,m 点有多少种不同的方法。
时间: 2023-06-17 07:08:27 浏览: 92
以下是用动态规划(Dynamic Programming)的方法来解决这个问题。
首先,我们可以定义一个二维数组 dp,其中 dp[i][j] 表示从起点 (1, 1) 走到 (i, j) 的不同路径数。因为从起点出发只能向下或者向右走,所以我们可以得到状态转移方程:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
其中 dp[i-1][j] 表示从 (1, 1) 走到 (i-1, j) 的路径数,dp[i][j-1] 表示从 (1, 1) 走到 (i, j-1) 的路径数。因为只能向下或者向右走,所以从 (1, 1) 走到 (i, j) 的不同路径数就是这两个值的和。
最后,我们只需要初始化 dp[1][1] = 1,然后按照上述状态转移方程来计算 dp[n][m] 即可。
下面是完整的 C++ 代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
vector<vector<int>> dp(n, vector<int>(m, 0));
dp[0][0] = 1;
for (int i = 1; i < n; i++) {
dp[i][0] = 1;
}
for (int j = 1; j < m; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
int main() {
int m, n;
cout << "请输入矩阵的行数和列数:";
cin >> n >> m;
cout << "从起点 (1, 1) 走到终点 (" << n << ", " << m << ") 的不同路径数为:" << uniquePaths(m, n) << endl;
return 0;
}
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)