UVA 10359 Tiling

UVA_10359

    我们令f(n)表示有n列时的放置种数，那么我们不妨考虑左边第一个位置如何放置。实际上一共有三种情况，这样就可以得到f(n)=f(n-1)+2*f(n-2)。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger[] f = new BigInteger[260];
        f[0] = new BigInteger("1");
        f[1] = new BigInteger("1");
        for(int i = 2; i <= 250; i ++)
            f[i] = f[i - 2].multiply(BigInteger.valueOf(2)).add(f[i - 1]);
        while(cin.hasNext())
        {
            int n = cin.nextInt();
            System.out.println(f[n]);
        }
    }
}