骨牌覆盖

coding>Java
650 词

题目描述

用一个1*3的骨牌去覆盖一个3*n的长方形，求所有可能的方案数,n的范围（n的范围 1<=n<=1000）方案数请输出对$1000000007$取模的结果

输入

n

  • 40%  数据 n<=20
  • 80% 数据 n<=100
  • 100%的数据 n<=1000

输出

所有可能方案数 对$1000000007$取模的结果

样例输入

1
3

样例输出

1
2

提示

递推，动态规划

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    final static BigInteger MOD = BigInteger.valueOf(1000000007);
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger[] f = new BigInteger[10000 + 1];
        int n = cin.nextInt();
        f[3] = BigInteger.valueOf(2);
        f[0] = f[1] = f[2] = BigInteger.ONE;
        for (int i = 4; i <= n; i++) {
            f[i] = f[i - 1].add(f[i - 3]).mod(MOD);
        }
        System.out.println(f[n]);
    }
}