骨牌鋪方格

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 68313 Accepted Submission(s): 32884

Problem Description

在2×n的一個長方形方格中,用一個1× 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數.
例如n=3時,為2× 3方格，骨牌的鋪放方案有三種,如下圖：

Input

輸入數據由多行組成，每行包含一個整數n,表示該測試實例的長方形方格的規格是2×n (0<n<=50)。

Output

對於每個測試實例，請輸出鋪放方案的總數，每個實例的輸出占一行。

Sample Input

1
3
2

Sample Output

1
3
2

典型斐波那契類遞歸問題（倒著看）
假設2 * n的長方形（除去n = 1；n = 2；的特殊情況，它實際就是2 * （n-1）再加上2 * 1的長方形，以此類推......

代碼樣例（註意類似斐波那契的數列增長很快，註意數據溢出。這裡我留了遞歸的兩種解決方法）

#include <bits/stdc++.h>
using namespace std;
#define N 50

long long nu[N]={1,2};
//long long arrange(int n)
//{
//  if(n == 1)
//      return 1;
//  if(n == 2)
//      return 2;
//  if(n > 2)
//      return arrange(n-1)+arrange(n-2);
//}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
    if(n > 2)
        {
            for(int i=2; i < n; i++)
            nu[i]=nu[i-1]+nu[i-2];
        }
            printf("%lld\n",nu[n-1]);
//      printf("%lld\n",arrange(n));
    }
return 0;
}

附：遞歸問題相關題目

1、（補題 杭電 2044）一隻小蜜蜂... 原題 HDU 2044 一隻小蜜蜂...

2、（杭電 2045）不容易系列之(3)—— LELE的RPG難題 原題 HDU 2045不容易系列之(3)—— LELE的RPG難題

3、（補題 杭電 2046）骨牌鋪方格 原題 HDU 2046 骨牌鋪方格