2019年中南大学研究生复试机试题
发布时间
阅读量：
阅读量
2019年中南大学研究生复试机试题
-
- 爬楼梯游戏
爬楼梯游戏
设有n级台阶, 小明从第一级台阶开始攀登至第n级台阶, 每步可以选择登上一级或两级台阶, 现在要求计算小明从第一级台阶到第n级台阶共有多少种不同的路径方式. 为了避免数值过大, 需要求解的答案需对p取模. 其中p的值设定为10^9+7.
输入
输入包含多组测试用例。
每组样例第一行输入楼梯的阶数n。(1<=n<=1000000)
输出
对于每组样例，输出方案数。最后结果对109+7取模。
样例输入
1
2
3
样例输出
1
2
3
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1000002;
int dp[maxn];//要先填充dp再进行多组输入，否则会超时
int main()
{
int n;
dp[0]=1,dp[1]=1;
for(int i=2;i<=1000000;i++)
dp[i]=(dp[i-1]+dp[i-2])%mod;
while(scanf("%d",&n)!=EOF)
printf("%d\n",dp[n]);
}全部评论 (0)
还没有任何评论哟~