UVa13141 - Growing Trees(動態規劃)

題目大意

目前正在做林地復育，大家給你一個任務是數每一個樹的其中一個 level 樹幹有幾個，而林地裡面的樹大多邏輯是這樣，觀察下面此圖找到邏輯

邏輯大概如下

• level 1 的樹，只會是一枝樹幹
• level i 的樹，如果這一枝樹幹不是透過上一層分裂而來，那 level i+1 要分裂成兩個樹幹
• level i 的樹，是透過上一層分裂而來，那 level i+1 不分裂

我們會問你 level i，請告訴我們那一層有幾個樹幹

題目大意

重點觀念

• 觀察 DP 邏輯

分析

• 稍微細心的解題者可以發現，這棵樹其實就是一個費式樹列，因此直接產生一個費式樹列即可。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 90
using namespace std;
int f[MAXN];
int n;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL

    f[1] = 1, f[2] = 1;
    for(int i = 3; i < MAXN; i++){
        f[i] = f[i-1] + f[i-2];
    }

    while(cin >> n && n){
        cout << f[n] << "\n";
    }
    return 0;
}