- 第 82 篇 -
Date: 2025 - 03 - 17
Author: 鄭龍浩/仟濹
【遞歸與動態規劃(DP) C/C++】

一 遞歸

我看的課程，如下視頻鏈接

https://www.bilibili.com/video/BV1LiS1YSEgF/?share_source=copy_web&vd_source=123565abb60ee9d849adaeb118d98b85

1基本介紹

是什么

遞歸就是函數自己調用自己。

核心

將大問題分解成規模更小的相同問題，直到達到可直接求解的簡單情況（如 n=1），再逐層返回結果。
優化 - 記憶化搜索

如果過程中會出現重復計算，則可以提前將重復計算保存下來

2 遞歸技巧

(1) 遞歸三步法

1. 定義基準條件(確定結束條件)

   明確遞歸終止的邊界條件（如 階乘時的n=1 ），避免無限遞歸

2. 假設子問題已解決
   將遞歸函數視為黑盒，直接假設它能返回子問題的正確結果（例如：算 f(n) 時，直接相信 f(n-1) 和 f(n-2) 是對的）

   說簡單點就是: 只管向問問題，它一定能返回正確答案。

3. 組合子問題的解(拆解問題)

   用子問題的解構建當前問題的解（如 return f(n-1) + f(n-2)）

   說簡單點就是: 把子問題的答案組合起來，得到當前問題的解

(2) 思維小技巧

無需提前理解完整遞歸過程！！！

我之前就陷入了這個問題。就是我在寫遞歸的時候，必須想清楚遞歸從頭到尾的所有過程和細節，其實沒有必要，直接當作這個遞歸函數已經存在且寫完

遞歸是「自相似性」的數學抽象，只需關注當前層邏輯，無需腦補調用棧細節（如 f(n-1) 內部如何實現）

不要陷入 “先有雞還是先有蛋“ 的思維陷阱！！！

一定要注意，我之前因為陷入這個思維陷阱，特別較真，特別想搞清楚具體過程，太沒必要了

• 直接假設遞歸函數已能正確工作（即使它尚未寫完），基于此設計當前邏輯。這種「信任遞歸」的思維是突破遞歸障礙的關鍵
• 即直接將沒寫完的遞歸函數當作已經有了的函數去寫，就認為這個函數是有答案的，這么去寫就可以了，無需把這個遞歸函數中的自身的函數當作遞歸函數
• 禁止：在編碼時腦補多級遞歸調用的堆棧狀態

3 例題

(1) 階乘 (純遞歸 or DP)

不使用記憶化搜索 Or 使用記憶化搜索

// 2025-03-16
#include <bits/stdc++.h>
using namespace std;
// 不使用記憶化搜索
long long funA( long long n ) {if (n == 1)return 1;return funA(n - 1) * n;
}
// 使用記憶化搜索
// 使用數組或哈希表記憶
unordered_map <long long, long long> memo;
long long funB( long long n ) {if (n == 1)return 1;if (memo.find(n) == memo.end()) {memo[n] = funB(n - 1) * n;}return memo[n];
}int main( void ) {long long n;cin >> n;// 不使用記憶化搜索cout << "不使用記憶化搜索的答案:" << funA(n) << '\n';// 使用記憶化搜索cout << "使用記憶化搜索的答案:" << funB(n) << '\n';return 0;
}

(2) 斐波那契數列 (純遞歸 or DP)

不使用記憶化搜索 Or 使用記憶化搜索

// 2025-03-16
#include <bits/stdc++.h>
using namespace std;
// 不使用記憶化搜索
long long funA( long long n ) {if (n <= 2) return 1;return funA(n - 1) + funA(n - 2);
}
// 使用記憶化搜索
// 使用數組或哈希表記憶
unordered_map <long long, long long> memo;
long long funB( long long n ) {if (n <= 2) return 1;if (memo.find(n) == memo.end())memo[n] = funB(n - 1) + funB(n - 2);return memo[n];
}int main( void ) {// 第n位斐波那契數字long long n;cin >> n;// 不使用記憶化搜索cout << "不使用記憶化搜索的答案:" << funA(n) << '\n';// 使用記憶化搜索cout << "使用記憶化搜索的答案:  " << funB(n) << '\n';return 0;
}

(3) 漢諾塔 (純遞歸 or DP)

必須要注意，打印的不是 前 n 個 圓盤從某個柱子移動到某個柱子，而是 第 n 個 圓盤從某個柱子移動到某個柱子。

我剛開始想了好久，就是這個地方理解錯了，我以為打印的是 前 n 個 圓盤，后來意識到是 第 n 個 圓盤以后，恍然大悟，理解了這個程序。

然后為了助于我理解，我又寫了一個中文打印過程版本，以免以后復習的時候，看到這個英文打印的代碼又理解錯了。

① 英文打印過程的版本

代碼

// 2025-03-16
// 輸入圓盤數量，三個柱子標識
// 打印圓盤的移動過程: 移動數量 from ? to ? ---> 錯誤理解
// 打印圓盤的移動過程: 第n個 from ? to ? （這個意思是第 n 個 從 ? 移動到 ？） --> 正確理解
// 注意：該題要求的是移動過程的輸出，而不是真的移動，所以不要鉆牛角尖，我想了半天為什么只打印不移動，實際人家要的結果就是打印
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char F, char A, char T) {if (n == 1) { // 遞歸終止條件：只剩一個盤子時直接移動// 打印：move 1 from A to C// 打印：移動第 n 個盤子到目標柱 Tprintf("move %d from %c to %c\n", n, F, T);return;}// 步驟1：將前 n-1 個盤子從 F 移到 A（借助 T 輔助）hanoi(n - 1, F, T, A); // 步驟2：打印：移動第 n 個盤子到目標柱 Tprintf("move %d from %c to %c\n", n, F, T);// 步驟3：將 n-1 個盤子從 A 移到 T（借助 F 輔助）hanoi(n - 1, A, F, T);
}
int main( void ) {int n, F, A, T;cout << "請輸入圓盤數量" << endl;cin >> n;getchar();cout << "請輸入起始柱、輔助柱、目標柱" << endl;scanf ("%c %c %c", &F, &A, &T);hanoi (n, F, A, T);return 0;
}

輸入與運行結果

請輸入圓盤數量
3
請輸入起始柱、輔助柱、目標柱
A B C
move 1 from A to C
move 2 from A to B
move 1 from C to B
move 3 from A to C
move 1 from B to A
move 2 from B to C
move 1 from A to C

② 中文打印過程的版本(為了避免自己以后復習的時候又理解錯誤，故寫了中文打印版本)

為了避免自己以后復習的時候又理解錯誤，故寫了中文打印版本

代碼

// 2025-03-16
// 輸入圓盤數量，三個柱子標識
// 打印圓盤的移動過程: 移動數量 from ? to ? ---> 錯誤理解
// 打印圓盤的移動過程: 第n個 from ? to ? （這個意思是第 n 個 從 ? 移動到 ？） --> 正確理解
// 注意：該題要求的是移動過程的輸出，而不是真的移動，所以不要鉆牛角尖，我想了半天為什么只打印不移動，實際人家要的結果就是打印
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char F, char A, char T) {if (n == 1) { // 遞歸終止條件：只剩一個盤子時直接移動// 打印：move 1 from A to C// 打印：移動第 n 個盤子到目標柱 Tprintf("將第 %d 個圓盤從 %c 柱子移動到 %c 柱子\n", n, F, T);return;}// 步驟1：將前 n-1 個盤子從 F 移到 A（借助 T 輔助）hanoi(n - 1, F, T, A); // 步驟2：打印：移動第 n 個盤子到目標柱 Tprintf("將第 %d 個圓盤從 %c 柱子移動到 %c 柱子\n", n, F, T);// 步驟3：將 n-1 個盤子從 A 移到 T（借助 F 輔助）hanoi(n - 1, A, F, T);
}
int main( void ) {int n, F, A, T;cout << "請輸入圓盤數量" << endl;cin >> n;getchar();cout << "請輸入起始柱、輔助柱、目標柱" << endl;scanf ("%c %c %c", &F, &A, &T);hanoi (n, F, A, T);return 0;
}

輸入與運行結果

請輸入圓盤數量
3
請輸入起始柱、輔助柱、目標柱
A B C
將第 1 個圓盤從 A 柱子移動到 C 柱子
將第 2 個圓盤從 A 柱子移動到 B 柱子      
將第 1 個圓盤從 C 柱子移動到 B 柱子      
將第 3 個圓盤從 A 柱子移動到 C 柱子      
將第 1 個圓盤從 B 柱子移動到 A 柱子      
將第 2 個圓盤從 B 柱子移動到 C 柱子      
將第 1 個圓盤從 A 柱子移動到 C 柱子