在2×n的一个长方形方格中，用一个1×2的骨牌铺满方格，输入n，输出铺放方案的总数。例如n=3时，骨牌的铺放方案有3种，如下图所示。

输入格式:

测试数据有多组，处理到文件尾。每组测试输入一个整数n（0<n≤50），表示长方形方格的规格是2×n。

输出格式:

对于每组测试，请输出铺放方案的总数，每组测试的输出占一行。

输入样例:

3
50

输出样例:

3
20365011074

出处:

HDOJ 2046

 

参考代码

#include <stdio.h>

// 定义一个足够大的数组来存储计算结果
long long dp[51];

// 初始化斐波那契数列的前两个数
void init() {
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= 50; i++) {
        // 状态转移方程
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}

int main() {
    init(); // 初始化斐波那契数列
    int n;
    while (scanf("%d", &n) != EOF) { // 处理到文件尾
        if (n > 0 && n <= 50) {
            printf("%lld\n", dp[n]); // 输出铺放方案的总数
        }
    }
    return 0;
}