UVA 12459 - Bees' ancestors

題目:

Maya 是一隻愛幫助朋友的蜜蜂。Maya 的好朋友 Willy 是一隻雄蜂。他剛發現他沒有爸爸，他覺得很困擾。

Maya 知道雌蜂有雙親 (一個爸爸和一個媽媽)，但是雄蜂則只有一個媽媽而沒有爸爸。這是因為未交配的雌蜂所產的卵會孵出雄蜂，但是受精的卵則會孵出雌蜂。

在 Maya 曉以大義之後，Willy 開始好奇他有多少祖先。他有一個媽媽，兩個祖父母 (一個祖父和一個祖母)。他也有三個曾祖父母。因為 Willy 很懶，不想做太多計算，他要請你寫個程式來幫他計算某一代的祖先一共有幾個。假設同一代的祖先之間沒有親戚關係。

Input
你的程式會收到一連串的正整數，一個一行，各自代表一個世代。世代的最大值為 80。輸入以 0 結束。

Output
對於每筆測資，你的程式要印出 Willy 在那個世代有幾個祖先。

Sample Input #1
1
2
3
0

Sample Output #1
1
2
3

C++ code:

**用遞迴可能會TLE**

#include <bits/stdc++.h>

using namespace std;

unsigned long f(unsigned int num) {

    if (num == 1) return 1;
    if (num == 2) return 2;

    unsigned long fib[num + 1];
    fib[1] = 1;
    fib[2] = 2;

    for (int i = 3; i <= num; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[num];
}

int main() {

    int a;
    while(cin >> a) {
        if (a == 0) {
            break;
        }
        else {
            cout << f(a) << endl;
        }
    }

    return 0;
}