链接:https://www.nowcoder.com/acm/contest/90/A 来源:牛客网
int Jump(int n)
{
if (n <= 0) return 0;
if (n == 1 || n == 2) return n;
return (Jump(n-1) + Jump(n-2));
}
但是这是实际就是个斐波那契数列的计算,这么算太慢,改成非递归即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
int Jump(int n)
{
if (n <= 0) return 0;
if (n == 1 || n == 2) return n;
return (Jump(n-1) + Jump(n-2));
}
int main()
{ ll dp[45],T,step;
dp[1]=1;
for(int i=2;i<40;i++)
{ dp[i]=1;
for(int j=i-1;j>=1;j--)
dp[i]+=dp[j];
}
cin>>T;
while(T--)
{
cin>>step;
cout<<dp[step]<<endl;
}
return 0;
}