【TFLSnoi李志帅】第⑤篇文章--递推算法经典例题

制作着实不易，不喜勿喷，欢迎点赞（嘿嘿嘿

1190：上台阶

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 23566     通过数: 6903

【题目描述】

楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

【输入】

输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。

【输出】

每一行输出对应一行输入的结果，即为走法的数目。

【输入样例】

1
2
3
4
0

【输出样例】

1
2
4
7

————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

满分代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n,a[76],i=1;//本题数据范围超出int，要用long long
    a[1]=1;a[2]=2;a[3]=4;//求出递推边界
    while (n)
    {
        
        cin>>n;
        if(n==0)break;
        for(int j=4;j<=n;j++)
        {
            a[j]=a[j-1]+a[j-2]+a[j-3];//由于第n级楼梯可以由第n-1，n-2，n-级楼梯一步跨上，所以第到达n级楼梯的方法为到达第n-1，n-2，n-3级楼梯的方法数之和
                                        //得出递推式为：f（n）=f（n-1）+f（n-2）+f（n-3） 当n=4时，f（n）=4+2+1=7，以此类推
        }
        cout<<a[n]<<endl;
    }
    return 0;
}