poj 2506 Tiling 递推

题目描述: http://poj.org/problem?id=2506

题目大意: 使用2 * 1 和 2 * 2 的矩形铺砌2 * n 的矩形, 共有多少种方法?

分析:
    假设f ( n ) 为铺砌 2 * ｎ　的矩形的方法种数，　参见下图：



易得 f ( n ) = f ( n - 1 ) + 2 * f ( n - 2 );
            f ( 1 ) = 1;         f ( 2 ) = 3;
      
       又因为本体要求处理的n 很大, 需要大数处理, 故用Java 的BigInteger 类, 免去用c++ 实现大数加法, 代价是牺牲一部分的性能...


注意f ( 0 ) 的取值, 参见代码

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

public class Main {
	public static void main(String[] args) {
		int n;  //2 * n 的 n
		BigInteger[] a = new BigInteger[251];
		a[0] = BigInteger.ONE;  //令人上火的是a[0] 为 1,??????
								//刚开始写a[0] 为  0,WA
		a[1] = BigInteger.ONE;
		a[2] = new BigInteger("3");
		
		for(int i = 3; i <= 250; i++) {
			a[i] = a[i - 1].add(a[i - 2].add(a[i - 2]));
		}
		Scanner in = new Scanner(System.in);
		while(in.hasNext()) {
			n = in.nextInt();
			System.out.println(a[n]);
		}
	}

}