首页 > 代码库 > poj2506 Tiling

poj2506 Tiling

题目大意:大意就是有2×1和2×2两种规格的地板,现要拼2×n的形状,共有多少种情况。

主要思路:2506与1953同属于找规律递推的题目,所以也可用设置数组记录每个下标所对应的情况(动态规划),不同的是由于这题涉及到大数,所以我用java的大数类很轻松解决,只不过有个坑是当n=0时,方案是1(惊不惊喜,意不意外?)。。。

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


public class Main {


    static BigInteger dp[] = new BigInteger[251];
    static void tile(){
        BigInteger flag = BigInteger.ONE;
        BigInteger three = new BigInteger("3");
        BigInteger two = new BigInteger("2");
        dp[0]=flag;
        dp[1]=flag;
        dp[2]=flag.multiply(three);
        for(int i=3;i<251;i++)
        {
            dp[i]=dp[i-1].add(dp[i-2].multiply(two));
            
        }
        
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        while(scan.hasNext()){
            int n=scan.nextInt();
            tile();
            
            System.out.println(dp[n]);
            
        }
        
    }

}

 

poj2506 Tiling