斐波那契數列是我們在編程中經常會遇到的一個經典問題。它的定義很簡單：第0項是0，第1項是1，從第2項開始，每一項都等於前兩項之和。用數學公式表示就是：f(0) = 0，f(1) = 1，當n > 1時，f(n) = f(n-1) + f(n-2)。
如果我們想計算f(5)，可以一步步算：f(2)=f(1)+f(0)=1+0=1，f(3)=f(2)+f(1)=1+1=2，f(4)=f(3)+f(2)=2+1=3，f(5)=f(4)+f(3)=3+2=5。這個過程看起來很簡單，但如果n變得很大，比如n=100，直接用這種方法計算會怎麼樣呢？
暴力遞歸法的問題¶
我們先嚐試用最簡單的遞歸方法來寫代碼：
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
這個方法的問題在於重複計算太多。比如計算f(5)時，fib(3)被計算了兩次，fib(2)被計算了三次；計算f(10)時，fib(5)會被計算多次。隨着n增大，重複計算的次數呈指數級增長，時間複雜度高達O(2^n)，幾乎不可用。
動態規劃的核心思想¶
動態規劃的核心是“記住已經解決過的子問題答案，避免重複計算”。就像我們做數學題時，如果遇到“已經算過的步驟”，就直接用結果，不用再從頭算一遍。
1. 記憶化遞歸（帶備忘錄）¶
我們可以用一個數組（備忘錄）來存儲已經計算過的斐波那契數。當需要計算f(n)時，先檢查備忘錄中是否已有結果，如果有就直接返回；如果沒有，計算後再存入備忘錄。
代碼實現：
int fib(int n) {
if (n <= 1) return n;
vector<int> memo(n + 1, -1); // 備忘錄數組，初始化爲-1表示未計算
return helper(n, memo);
}
int helper(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // 已計算過，直接返回
memo[n] = helper(n - 1, memo) + helper(n - 2, memo); // 計算並存儲結果
return memo[n];
}
這個方法中，每個f(k)只計算一次，時間複雜度是O(n)，空間複雜度是O(n)（備忘錄數組）。
2. 遞推法（從底向上迭代）¶
更高效的方法是迭代。因爲斐波那契數列的每一項只依賴前兩項，我們可以用兩個變量記錄前兩項的值，依次迭代計算下一項，無需額外數組空間。
代碼實現：
int fib(int n) {
if (n <= 1) return n;
int a = 0; // f(0)
int b = 1; // f(1)
for (int i = 2; i <= n; ++i) {
int c = a + b; // 計算當前項
a = b; // 更新前一項
b = c; // 更新當前項
}
return b;
}
這個方法的時間複雜度是O(n)，空間複雜度是O(1)，是最優解法。
動態規劃的關鍵特性¶
通過斐波那契數列，我們能理解動態規劃的兩個核心特性：
1. 重疊子問題：大問題分解爲小問題，且小問題會被重複計算（如f(3)在計算f(5)和f(4)時都需要）。
2. 最優子結構：當前問題的解依賴於子問題的解（f(n) = f(n-1) + f(n-2)）。
總結¶
動態規劃的本質是用空間換時間，通過存儲子問題的結果避免重複計算。斐波那契數列是動態規劃的經典入門案例，從暴力遞歸到記憶化遞歸再到遞推法，每一步都體現了優化的思路。掌握這個方法後，我們可以解決更復雜的問題，如爬樓梯、最長公共子序列等。
從現在開始，嘗試用動態規劃思想解決更多實際問題吧！