A30644-题解（详细解析）

解析

递推的意义就是找规律，那让我们先列几个例子看看
比如说：
1个台阶，他只能走1步（1阶），因此走法数量为1。
2个台阶，既可以2个1阶走完，也可以一次性上2阶，因此走法数量为2
3个台阶，既可以3个1阶走完，也可以一次性上3阶，还可以先走两阶再走一阶，甚至还可以反着，因此走法数量为4
现在，多列几个，如下图所示

台阶数量	走法数量	公式
1	1	初始
2	2	初始
3	4	初始
4	7	1+2+4
5	13	2+4+7

继续写下去，你会发现，除台阶数1,2,3外，后面的走法数量都等于前面三个走法数量的和。
比如台阶数量为4，走法数量就为1+2+4=7，那不就是斐波那契数列Plus嘛！
所以，聪明的你已经知道代码怎么写了吧？

代码解析

首先，导入头文件。

#include<bits/stdc++.h>
using namespace std;

然后，让我们来创建一个int数组f，用来存储台阶数量，

int f[60];

main函数内，我们发现，前3个数据根本就没有办法按照规律计算，因为他们前面的数都没有三个。
所以，我们直接将他提前设置好。这也是我们后面计算的基础

int main(){
    f[1] = 1;
    f[2] = 2;
    f[3] = 4;

随后，我们使用for循环，按照f[i]=前三项之和的规律计算

请注意循环范围，前面三项的数据我们已经设置好，此处循环应该从第四项开始

先循环完再计算是为了减少时间，避免反复循环造成的超时

    for(int i=4;i<=20;i++){
        f[i] = f[i-1] + f[i-2] + f[i-3];
    }

最后，我们使用死循环while(true)，在循环里面创建一个变量n
输入n之后，如果为0，则按照题目要求结束循环，否则输出相应的f[n]数据。

while(true)本身不是死循环的意思，true的条件只是保证循环判断条件一直为真，请注意。

    while(true){
        int n;
        cin >> n;
        if(n==0) break;
        cout << f[n] << endl;
    }

最后，让我们结束程序，解决！

    return 0;
}

---

完整代码

这个题是我好久之前写的了，所以代码没有注释，请谅解qwq

#include<bits/stdc++.h>
using namespace std;
long long f[60];
int main(){
    f[1] = 1;
    f[2] = 2;
    f[3] = 4;
    for(int i=4;i<=20;i++){
        f[i] = f[i-1] + f[i-2] + f[i-3];
    }
    while(true){
        int n;
        cin >> n;
        if(n==0) break;
        cout << f[n] << endl;
    }
}

---

祝题题AC！