斐波那契數列法（最優法）

甚至可以不要循環，直接用斐波那契數列通式算出答案

#include <stdio.h>

int main()
{
    int n = 4;    // 臺階數
    int p = 0, q = 1;    // 斐波那契數列的第 0, 1 項

    // 求斐波那契數列（1, 1, 2, 3, 5, ...）的第 n+1 項
    for (int i = 0; i < n; i++)
    {
        // p, q 所代表的項向前移動
        int sum = p + q;
        p = q;
        q = sum;
    }

    printf("%d", q);

    return 0;
}

遞歸法（數組優化重複計算）

遞歸法耗時長，重複計算多，且 n 過大時會爆棧。唯一的優點是寫起來稍微簡單一點，但是如果要優化的話也簡單不到哪去。

#include <stdio.h>

// 青蛙上 n 級臺階有幾種走法
int Frog(int n)
{
    static int ret[1024] = { 0 };

    if (n < 1024 && ret[n] != 0)
        return ret[n];

    int r;
    if (n <= 2)
        r = n;
    else
        r = Frog(n - 1) + Frog(n - 2);
    if (n < 1024)
        ret[n] = r;

    return r;
}

int main()
{
    int m;
    scanf("%d", &m);

    printf("%d", Frog(m));

    return 0;
}