每次只能走1阶或2阶，有多少种方法走完
这个问题笔试时经常会问到，使用c++如何实现呢？
该回答引用ChatGPT
楼梯问题是一个经典的递归问题，即一个人每次可以走一阶或两阶，问他到达 n 阶楼梯的方法数。
#include <iostream>
using namespace std;
int stairs(int n)
{
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else if (n == 2)
return 2;
else
return stairs(n-1) + stairs(n-2);
}
int main()
{
int n;
cout << "Enter the number of stairs: ";
cin >> n;
cout << "The number of ways to reach the top is: " << stairs(n) << endl;
return 0;
}
测试下面代码
1.方法一：采用递归的方式
走到第n阶时可能是从第n-1阶走一步到的，也可能是从n-2阶走两阶到的，设F(n)为走到n阶的种数，则F(n)=F(n-1)+F(n-2)。当n=1时，F(1)=1，n=2时，F(2)=2，这是一个动态规划问题。其实就是一个斐波那契数列。
#include <iostream>
long long func(int n)
{
if(1 == n || 2 == n)
{
return n;
}
else if(n > 2)
{
return func(n - 1) + func(n - 2);
}
else
{
return -1; // n 非法
}
}
int main()
{
std::cout << func(50) << std::endl; // 输出20365011074
system("pause");
return 0;
}
2.方法二：采用非递归的方式
int main()
{
long long a[90];
int n = 50;
a[1] = 1;
a[2] = 2;
for(int i = 3; i <= n; i++)
{
a[i] = a[i-1]+a[i-2];
}
std::cout << a[n] <<std::endl; // 输出20365011074
system("pause");
return 0;
}
```c++
```
不知道你这个问题是否已经解决, 如果还没有解决的话: