骨牌覆盖

/*在2*N的一个长方形方格中，用一个1*2的骨牌排满方格。
问有多少种不同的排列方法。

例如：2 * 3的方格，共有3种不同的排法。（由于方案的数量巨大，只输出 Mod 10^9 + 7 的结果）

Input
输入N(N <= 1000)
Output
输出数量 Mod 10^9 + 7
Input示例
3
Output示例
3
思路：对于第x块骨牌的情况，我们用a[x]表示其方法数；其比x-1块骨牌时多了一块骨牌，多出的骨牌有两种放法：
１．我们可以直接将其竖着添加在最末端，那么其排列数就为就是前x-1块骨牌的排列数，即为a[x-1]；
２.　我们也可以将其和其前面一块骨牌一起横着放，那么其排列数就是前x-2块骨牌的排列数，即为a[x-2]；
所以有　a[x]=a[x-1]+a[x-2]；*/
package test;

import java.util.Scanner;

public class 骨牌覆盖 {
    static int mod=(int) (1e9+7);
    static int MAX=1010;
    public static void main(String arg[]){
        Scanner input=new Scanner(System.in);
        int[] a=new int[MAX];
        int n;
        a[0]=1; a[1]=1;
        n=input.nextInt();
        for(int i=2; i<=n; i++){
            a[i]=(a[i-1]+a[i-2])%mod;
        }
        System.out.println(a[n]);;
    }
}