小明爬楼梯（4）（递推）

题目描述

小明很喜欢爬楼梯，这一次，他获得了一个特异功能，每次可以跳跃1、4、7、10、...级阶梯。

比如他初始在楼底，跨越一个阶梯到达 1 号阶梯，或者跨越 4 个楼梯到达 4 号阶梯。

为了选出一种最轻松的爬楼梯的方式，小明想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 n 个阶梯的楼梯，小明一共有多少总方法从楼底到达楼顶。

由于最后答案可能很大，输出最后的答案对 100007 取模的结果。

输入格式

一行，一个整数 n（n<=100000），表示一共有 n 级台阶。

输出格式

输出最后答案对于 100007 取模的结果。

输入样例1

5

Copy

输出样例1

3

Copy

输入样例2

47176

Copy

输出样例2

74412

题解

每层楼梯方式数量

1. 1

2. 1

3. 1

4. 2

5. 3

6. 4

7. 6

8. 9

由此可推出a[i]=a[i-1]+a[i-3]+a[5]；

代码

#include<bits/stdc++.h>
using namespace std;
 int a[100001];
int main(){
	int n;
	cin>>n;
    a[1]=1;
    a[2]=1;
    a[3]=1;
    for(int i=4;i<=n;i++){
        a[i]=(a[i-1]+a[i-3])%100007;
    }
    cout<<a[n]%100007;
	return 0;
}

点个关注吧 ！！！！！！！！！！！！！！！！！！！（（（（；