题目描述 

继上次Jhadgre在楼梯上跳台阶玩了很久之后，他获得了一个很强(la)力(ji)的能力，那就是上楼梯的时候可以跨任意偶数级台阶….

今天上完课,Jhadgre又开始了他的跳台阶之旅，现在他想知道跳到第N级台阶有多少种方案数。

P.S.Jhadgre从楼梯外也就是第0级开始跳，并且依旧可以选择跳一级

输入描述:

多组数据(<=100组)，每组数据包含一个整数N(2<=N<=10000)

输出描述:

对于每组数据包含一个整数表示跳到第N级台阶的方案数（答案对100000007取模）

示例1

输入

3
4 

输出

3
6

题解：对于第n级台阶，他的所有方案和为：跳到第n-1级台阶的方案数（跳一级）+ n-2,n-4,n-6,n-8….（跳偶数级）的方案数。

比如7，那么他的次数就是6，5，3，1加起来；
对于8，就是7，6，4，2，0加起来

以下是比赛时提交的代码：

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
#define maxn 1e8+10
#define PI acos(-1.0)
using namespace std;
 
ull a[10010],sumj=0,sumo=0;
void work(){
    a[1]=1;
    a[2]=2;
    sumj += a[1];
    sumo += a[2];
    for(int i = 3;i<=10000;i++){
        a[i] += a[i-1];
        if(i%2){
            a[i]+= sumj;
            sumj += a[i];
        }
        else{
            a[i]+= sumo+1;
            sumo += a[i];
        }
        sumj %= 100000007;
        sumo %= 100000007;
        a[i] %= 100000007;
    }
}
 
int main()
{
    work();
    int n;
    while(~scanf("%d",&n)){
        printf("%lld\n",a[n]);
    }
    return 0;}

以下是简洁的标程：

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 100000007;
int dp[10100];
int main() {
int n;
 dp[0] = 1;
 for (int i = 1; i <= 10000; ++i) {
 dp[i] = dp[i - 1];
 for (int j = i - 2; j >= 0; j -= 2) {
 dp[i] += dp[j];
 dp[i] %= mod;
 }
 }
 while (cin>>n)
 cout << dp[n] << endl;
 return 0;
}