剣指Offer-9度1390-矩形カバー

 Offer-9 1390- カバー
2014-02-05 23:27

タイトルの説明:
2*1の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の2*1の小さい矩形で重ならずに1個の2*nの大きい矩形を覆って、全部で何種類の方法がありますか?
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は、nが偶数である整数n(1<=n<=70)を含む.
出力:
各テストケースに対応し、
出力はn個の2*1の小さな矩形で1個の2*nの大きな矩形を重ならずに覆い、合計である方法数である.
サンプル入力:

4

サンプル出力:

5

 ：
　　 フィボナッチ  ， 。
　　 O(n)， O(1)， O(n)。

 1 // 688894    zhuli19901106    1390    Accepted     case     1020KB    362B    0MS

 2 // 201402020104

 3 #include <cstdio>

 4 #include <cstdlib>

 5 using namespace std;

 6 

 7 int main()

 8 {

 9     const int MAXN = 71;

10     long long int res[MAXN];

11 

12     res[0] = res[1] = 1;

13     int i;

14     for (i = 2; i < MAXN; ++i) {

15         res[i] = res[i - 2] + res[i - 1];

16     }

17 

18     while (scanf("%d", &i) == 1) {

19         printf("%lld
", res[i]);

20     }

21 

22     return 0;

23 }