4.1 遞推法概述
設計思想：
遞推法（Recurrence Method）通過已知的初始條件和遞推關系，逐步推導出問題的最終結果，常用于序列計算和分階段問題求解。
示例：猴子和桃子問題
題目描述：
猴子每天吃掉剩余桃子的一半再多吃一個，第 10 天只剩 1 個桃子，問最初有多少個桃子？
思路：
-
設 a[n] 為第 n 天結束后剩余的桃子數；
-
已知 a[10] = 1；
-
從后向前有遞推關系：
a[n] = (a[n+1] + 1) × 2
代碼實現：
// MonkeyPeach：計算第1天最初的桃子數
int MonkeyPeach(int days) {// days 表示總共天數，本題為 10int peaches = 1; // 從第 days-1 天開始倒推到第 1 天for (int day = days - 1; day >= 1; day--) {// 根據遞推關系 a[n] = (a[n+1] + 1) * 2// peaches 此時保存 a[n+1]，更新后即為 a[n]peaches = (peaches + 1) * 2;}return peaches;
}
整體解釋：
我們先假設最后一天剩余 1 個桃子，然后按照“后一天的桃子數加 1 再乘 2”這個公式，依次向前推算，每一步都將當前天的剩余數計算出來，循環結束后 peaches 即為第 1 天最初的桃子數。
4.2 數學序列中的遞推法
4.2.1 斐波那契數列
題目描述：
兔子繁殖問題：第 1、2 個月各有 1 對兔子，從第 3 個月起每月新增的兔子對數等于前兩個月兔子對數之和，求第 n 個月的兔子對數。
遞推關系：
f(1) = 1, f(2) = 1
f(n) = f(n-1) + f(n-2), n ≥ 3
代碼實現：
// Fibonacci：計算第 n 個月的兔子對數
int Fibonacci(int n) {// 前兩個月的兔子對數均為 1if (n <= 2) return 1;int prev = 1; // f(i-2)int curr = 1; // f(i-1)int next; // f(i)// 從第 3 個月開始循環for (int i = 3; i <= n; i++) {next = prev + curr; // 應用 f(i) = f(i-1) + f(i-2)prev = curr; // 將 f(i-1) 賦值給 prevcurr = next; // 將 f(i) 賦值給 curr}return curr; // 返回 f(n)
}
整體解釋：
我們只記錄前兩項 prev 和 curr，每次計算新的一項 next，然后滾動更新這兩個變量，最后 curr 存儲的就是第 n 個月的兔子對數。此方法空間復雜度 O(1)，時間復雜度 O(n)。
4.2.2 卡塔蘭數
題目描述：
凸 n 邊形劃分成三角形的不同方式數，第 n 個卡塔蘭數 C(n) 滿足：
C(0) = 1
C(n) = ∑_{i=0}^{n-1} C(i) × C(n-1-i), n ≥ 1
代碼實現：
// Catalan：計算第 n 個卡塔蘭數
int Catalan(int n) {// 分配數組存儲 0...n 的 C 值int C[n+1];C[0] = 1; // C(0) = 1// 依次計算 C(1) 到 C(n)for (int i = 1; i <= n; i++) {C[i] = 0;// 按定義累加for (int k = 0; k < i; k++) {C[i] += C[k] * C[i - 1 - k];}}return C[n];
}
整體解釋：
使用數組 C[] 自底向上存儲卡塔蘭數，通過兩層循環，外層決定要計算的下標 i，內層按公式累加前面各項乘積，最終 C[n] 即為答案。時間復雜度 O(n2)，空間復雜度 O(n)。
4.3 組合問題中的遞推法
4.3.1 錯排問題
題目描述：
有 n 封信和 n 個信封，要求沒有信件放入正確的信封，求錯排方案數 D(n)，遞推關系：
D(1) = 0
D(2) = 1
D(n) = (n - 1) × (D(n-1) + D(n-2)), n ≥ 3
代碼實現：
// Derangement：計算錯排數 D(n)
int Derangement(int n) {if (n == 1) return 0; // D(1) = 0if (n == 2) return 1; // D(2) = 1int dn_2 = 0; // D(n-2)int dn_1 = 1; // D(n-1)int dn; // D(n)// 從 n=3 開始迭代for (int i = 3; i <= n; i++) {dn = (i - 1) * (dn_1 + dn_2);dn_2 = dn_1; // 滾動更新 D(n-2)dn_1 = dn; // 滾動更新 D(n-1)}return dn; // 返回 D(n)
}
整體解釋：
只需保留前兩項 dn_2、dn_1，用遞推公式計算當前項 dn，再向后滾動即可，空間復雜度 O(1)，時間復雜度 O(n)。
4.3.2 旋轉萬花筒
題目描述：
起始有 4 個閃光點，每次旋轉在每個分支末端增加 2 個閃光點，問 n 次旋轉后總閃光點數。
代碼實現：
// Kale：計算旋轉 n 次后的閃光點總數
int Kale(int n) {int lamps = 4; // 初始閃光點數int addLamp = 2; // 每個分支基礎新增數for (int i = 1; i <= n; i++) {// 本次新增數量是上次的兩倍addLamp *= 2;// 累加到總閃光點數lamps += addLamp;}return lamps;
}
整體解釋：
變量 addLamp 跟蹤每次新增的閃光點數，每次翻倍后累加到 lamps，循環結束后 lamps 為旋轉 n 次的總數。時間復雜度 O(n)。
4.4 拓展與演練
4.4.1 整數拆分（2 的冪次劃分）
題目描述：
將正整數 n 拆分為若干 2 的冪次之和，求拆分方案數 d(n)，遞推關系：
d(1) = 1
d(2) = 2
若 i 為奇數: d(i) = d(i - 1)
否則: d(i) = d(i - 1) + d(i / 2)
代碼實現：
// PowerSplit：計算 2 的冪次拆分方案數
int PowerSplit(int n) {int d[n + 1]; // 存儲從 1 到 n 的方案數d[1] = 1; // d(1) = 1d[2] = 2; // d(2) = 2for (int i = 3; i <= n; i++) {if (i % 2 != 0) {// 奇數只能繼承前一個的方案d[i] = d[i - 1];} else {// 偶數可在繼承前一個方案基礎上，加上包含 i/2 的拆分d[i] = d[i - 1] + d[i / 2];}}return d[n];
}
整體解釋：
用一維數組 d[] 自底向上記錄每個 i 的方案數，遇到奇數直接復制，偶數則累加前一項和 i/2 的方案即可。時間復雜度 O(n)，空間 O(n)。
4.4.2 捕魚問題
題目描述：
5 人輪流捕魚，每人將看到的魚分成 5 份，丟棄 1 條并帶走 1 份，其余留給下一人，直到最后一人也按此規則操作，求最少的初始魚數及每人捕魚時看到的魚數。
思路：
從最小可能的初始魚數開始嘗試，依次驗證每個人都能整除且滿足規則。
代碼實現：
// GetFish：計算最少的初始魚數
int GetFish(int nPeople) {int fish[5]; // fish[i] 記錄第 i+1 個人見到的魚數fish[0] = 1; // 從最少 1 條開始嘗試while (1) {fish[0]++; // 逐次增加初始魚數bool valid = true;// 驗證每個人是否都能按規則操作for (int i = 1; i < nPeople; i++) {// (看見數 - 1) 必須能被 5 整除if ((fish[i - 1] - 1) % 5 != 0) {valid = false;break;}// 每人帶走1份，留給下一個的人 = (fish[i-1]-1)/5*4fish[i] = (fish[i - 1] - 1) / 5 * 4;}if (valid) break; // 全部滿足則結束循環}return fish[0];
}
整體解釋：
數組 fish[] 存儲每個人見到的魚數，從第一個人開始試探最小初始值，每次嘗試后向下驗證，若所有人都滿足“(見到數-1) 能被 5 整除”，則該初始值即為答案。時間復雜度較高，但能夠找到最小解。
