C++算台阶有多少种走法的代码如何写
时间: 2024-02-15 12:04:12 浏览: 19
可以使用动态规划的思想来解决这个问题。具体来说,我们可以定义一个长度为 n+1 的数组 dp,其中 dp[i] 表示走到第 i 个台阶有多少种走法。根据题目要求,我们可以得到以下状态转移方程:
dp[i] = dp[i-1] + dp[i-2]
其中,dp[0] = 1,dp[1] = 1,表示在第 0 个台阶和第 1 个台阶都只有一种走法。
下面是 C++ 的代码实现:
```cpp
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
```
该函数的输入参数是一个整数 n,表示有多少个台阶。函数返回一个整数,表示走完 n 个台阶有多少种不同的走法。
相关问题
n阶台阶每次走一步或两步c++
以下是一个简单的 C++ 代码示例,可以求解n阶台阶每次走一步或两步的不同走法数量:
```c++
#include <iostream>
using namespace std;
int main() {
int n;
cout << "请输入台阶数:";
cin >> n;
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
cout << "不同走法数量为:" << dp[n] << endl;
return 0;
}
```
该代码使用动态规划的思想,将n阶台阶的问题转化为求解斐波那契数列的第n项。其中,dp[i] 表示在第 i 阶台阶时的不同走法数量。由于每次只能走一步或两步,因此到达第 i 阶台阶的走法数量只能从第 i-1 阶和第 i-2 阶转移而来。最终,dp[n] 就是所求的不同走法数量。
楼梯有 n (30 > n > 0) 阶台阶,上楼时可以一步上 1 阶,也可以一步上 2 阶,也可以一步上 3 阶,编程计算共有多少种不同的走法。c++简单代码
以下是用 C++ 实现的动态规划解法:
```c++
#include <iostream>
using namespace std;
int count_ways(int n) {
if (n < 0) {
return 0;
}
if (n == 0) {
return 1;
}
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
return dp[n];
}
int main() {
int n = 4;
cout << "Number of ways to climb " << n << " stairs: " << count_ways(n) << endl;
return 0;
}
```
其中,变量 `dp` 为动态规划数组,`dp[i]` 表示走到第 `i` 阶台阶的不同走法数量。
当 `n=4` 时,输出为:
```
Number of ways to climb 4 stairs: 7
```
表示走到第4阶台阶有7种不同的走法。