d212: 東東爬階梯

題目連結: https://zerojudge.tw/ShowProblem?problemid=d212

# 內容

東東有個嗜好，爬階梯不是一次走一階，就是一次走兩階。

換句話說，假設階梯有三階，那他有三種走法

1. 第一步走一階，第二步走二階。
2. 第一步走二階，第二步走一階。
3. 全程都走一階。

這題要問你，假設階梯有 n 階，那東東有幾種走法？

# 輸入

第一行有一個正整數 n，0 < n < 100，表示階梯有 n 階。

# 輸出

請輸出 n 個階梯有幾種走法。

# 解題思路

走的方式數剛好會形成費氏數列 (第 n 項 = 第 n-1 項 + 第 n-2 項，n>=3)

運用 DP 觀念，依序把各層走法數給紀錄下來

# 程式碼

#include <iostream>

using namespace std;

int main()

{

    int n;

    unsigned long long int f[100]={1,1};

    for(int i=2;i<100;i++)

        f[i]=f[i-1]+f[i-2];

    while(cin >> n)

        cout << f[n] << endl;

    return 0;

}