题目描述

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1031

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题 收藏 关注
在2*N的一个长方形方格中，用一个1*2的骨牌排满方格。
问有多少种不同的排列方法。

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

Input
输入N(N <= 1000)
Output
输出数量 Mod 10^9 + 7
Input示例
3
Output示例
3

解题思想

/* 像这种题最开始一看就没有啥思路的， 就找一下看有没有规律，找一下当n=1,2,3,4 时，结果会发现结果是1,2,3,5 发现规律了吧，就是斐波拉切数列 */

代码

//递推写法
import java.util.Scanner;
public class Main{
    static final int mod = 1000000007;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        if(N > 0)
        a[0] = 1;
        if(N > 1)
          a[1] = 2;
        for(int i=2; i<N; ++i)
           a[i] = (a[i-1] + a[i-2]) % mod;
        System.out.println(a[N-1]);
    }
}