package com.demo2;
import java.util.Scanner;
/*
*在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,输入n ,输出铺放方案的总数.
 */
public class HDU_oj2046 {
	public static void main(String[] args) {
		Scanner sn = new Scanner(System.in);
		while(sn.hasNext()) {
			int n = sn.nextInt(); //表示该测试实例的长方形方格的规格是2×n (0<n<=50)
			/*
			 * n=1,1
			   n=2,2
			   n=3,3
    	 	   n=4,5
			 */
			System.out.println(compute(n));
		}
		sn.close();
	}
	static long[] arr = new long[60];
	public static long compute(int n) {
		if(arr[n] != 0)
			return arr[n];
		if(n==1)
			return arr[n] = 1;
		else if(n == 2)
			return arr[n] = 2;
		else
			return arr[n] = compute(n-1) + compute(n-2);
	}
}

又是一道递推题