poj 2506 Tiling 递推

scott________

题目描述: 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 的 nBigInteger[] a = new BigInteger[251];a[0] = BigInteger.ONE;  //令人上火的是a[0] 为 1,??????//刚开始写a[0] 为  0,WAa[1] = BigInteger.ONE;a[2] = new BigInteger("3");for(int i = 3; i <= 250; i++) {a = 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]);}}}