青蛙跳台階：斐波那契遞推與動態規劃優化

題目描述

青蛙一次跳1級或2級台階，求跳上n級台階的總方法數。n為輸入目標。

遞推關係建立

設f(n)為跳上n級的方法數。最後一步只能從n-1級（跳1級）或n-2級（跳2級）到達：
f(n) = f(n-1) + f(n-2) （n > 2）
邊界：f(1)=1, f(2)=2。
這正是斐波那契數列（起始項偏移）。

解法一：遞歸（指數級，不可取）

public int JumpFloor(int n) {
    if (n <= 0) return 0;
    if (n <= 2) return n;
    int a = 1, b = 2; // f(1), f(2)
    for (int i = 3; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

運行時間~33ms，僅O(n)時間、O(1)空間。滾動數組思想：只保留前兩狀態。

進階：矩陣快速冪求第n項 O(log n)