題?描述

?只?蛙?次可以跳上1 級臺階，也可以跳上2級……它也可以跳上n級。求該?蛙跳上?個n級的臺階總共有多少種跳法。

思路及解答

數學歸納法

?先?蛙?次可以跳 1 , 2 , 3 到 n 級。假設函數是f(n) ，則：

• ?蛙跳到第?級是f（1）=1 ，只有?種跳法。
• ?蛙跳到第?級，可以是直接跳到第?級，也可以是從第?級直接跳。所以f(2)=f(1)+1
• ?蛙跳到第三級，可以從第0 級跳，也可以從第1級跳，也可以從第2 級跳。所以f(3)=f(1)+f(2)+1 ;
• 依次類推，?蛙跳到第n 級，可以是從0 , 1 , 2 , 3 .. (n-1) 級跳，所以f(n)=f(1)+f(2)+f(3)...+f(n-1)+1 ;

進一步觀察可以發現：

• f(1) = 1
• f(2) = f(1) + f(0) = 2
• f(3) = f(2) + f(1) + f(0) = 4
• f(4) = f(3) + f(2) + f(1) + f(0) = 8

顯然，這是一個等比數列，通項公式為f(n) = 2^(n-1)。這個發現將問題簡化為簡單的冪次計算

public class Solution {
    public int JumpFloorII(int target) {
			if (target <= 0) return 0;
        return (int) Math.pow(2, target - 1);
    }
}

• 時間復雜度：O(1)，直接計算冪次
• 空間復雜度：O(1)，僅使用常數空間

數學歸納法的優勢在于將問題轉化為已知的數學公式，但需要較強的數學觀察能力才能發現其中的規律

遞歸

將大問題分解為小問題來解決。對于n級臺階，青蛙第一次跳躍可以有n種選擇：跳1級、跳2級，...，跳n級。如果第一次跳1級，剩下n-1級有f(n-1)種跳法；如果第一次跳2級，剩下n-2級有f(n-2)種跳法；依此類推，直到第一次直接跳n級，有1種跳法。

因此，遞歸公式為： f(n) = f(n-1) + f(n-2) + ... + f(1) + 1

而f(n-1) = f(n-2) + ... + f(1) + 1

兩式相減可得：f(n) = 2*f(n-1)，

public class Solution {
    public int JumpFloorII(int target) {
		if (target <= 0) return 0;
        if (target == 1) return 1;
        return 2 * jump(target - 1);
    }
}

• 時間復雜度：O(n)，需要n次遞歸調用
• 空間復雜度：O(n)，遞歸調用棧深度為n

遞歸解法雖然代碼簡潔，但當n較大時會出現棧溢出風險，且存在大量重復計算，效率較低

動態規劃

根據遞歸分析，我們已經知道f(n)=2*f(n-1)。因此，可以從f(1)開始，逐步計算f(2), f(3), ..., f(n)，每次利用前一次的結果

動態規劃可以將問題分解為重疊的子問題，并存儲子問題的解。

初始化：

• f(1) = 1
• 遞推關系：f(n) = 2 * f(n-1) for n > 1

這種方法避免了遞歸的重復計算，通過迭代方式自底向上構建解

public class Solution {
    public int JumpFloorII(int target) {
		if (target <= 0) return 0;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            dp[i] = 2 * dp[i - 1];
        }
        return dp[target];
    }
}

• 時間復雜度：O(n)，單層循環
• 空間復雜度：O(n)，需要dp數組存儲中間結果

動態規劃是遞歸解法的優化版本，適合大規模輸入

優化的動態規劃：優化空間復雜度

觀察動態規劃解法，發現計算f(n)只需要前一個狀態f(n-1)，不需要保存整個dp數組。因此可以用單個變量代替數組，實時更新當前值。

這種優化基于"滾動數組"思想，只保留必要的中間結果，可以將空間復雜度從O(n)降到O(1)。

public class Solution {
    public int JumpFloorII(int target) {
		if (target <= 0) return 0;
        int result = 1;
        for (int i = 2; i <= target; i++) {
            result *= 2;
        }
        return result;
    }
}

• 時間復雜度：O(n)，單層循環
• 空間復雜度：O(1)，僅使用常數空間

這是最優的迭代解法，應該也是面試官最想要看到的解法。