Java 經典演算法：青蛙跳台階問題與斐波那契數列實現

青蛙跳台階：一道經典的遞歸與動態規劃入門題

在 Java 程式設計基礎中，「青蛙跳台階」是一道極具代表性的練習題。題目描述：一隻青蛙一次可以跳 1 級台階，也可以跳 2 級。求該青蛙跳上一個 n 級台階總共有多少種跳法？這道題不僅考察遞歸思維，更是斐波那契數列在實際場景中的直接應用。

核心邏輯分析

我們可以從最簡單的情況開始推導：

• 當 n = 1 時，只有 1 種跳法（直接跳 1 級）
• 當 n = 2 時，有 2 種跳法（1+1 或直接跳 2 級）
• 當 n > 2 時，青蛙到達第 n 級台階，最後一步只能從第 n-1 級跳 1 級上來，或從第 n-2 級跳 2 級上來

由此得到遞歸公式：

f(n) = 1                    (n = 1)
f(n) = 2                    (n = 2)
f(n) = f(n-1) + f(n-2)      (n > 2, n 為整數)

Java 程式碼實現

以下是使用遞歸方式實現的完整程式碼：

public class FrogJump {
    public static void main(String[] args) {
        int n = 20; // 測試資料：20 級台階
        System.out.println("跳法總數: " + jumpFloor(n));
    }

    public static int jumpFloor(int target) {
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else if (target == 2) {
            return 2;
        } else {
            return jumpFloor(target - 1) + jumpFloor(target - 2);
        }
    }
}

效能考量與優化方向

雖然遞歸寫法直觀易懂，但存在大量重複計算，時間複雜度為 O(2^n)。實際開發中建議採用以下優化：

• 記憶化遞歸：使用陣列或 Map 緩存已計算結果
• 動態規劃（自底向上）：迭代計算，空間複雜度可優化至 O(1)
• 矩陣快速冪：將時間複雜度降至 O(log n)

這道題目完美展示了如何將生活場景抽象為數學模型，再轉化為程式邏輯，是演算法入門的絕佳練習。