🧩 動態規劃實戰
動態規劃 (Dynamic Programming) 是電腦科學中最重要也最優雅的演算法設計方法。
「那些不會 DP 的工程師，遇到複雜問題時只能寫出 O(2ⁿ) 的暴力解；而會 DP 的工程師，能用 O(n²) 優雅解決。」
DP 的核心思想很簡單：把大問題拆解成小問題，記住小問題的答案，避免重複計算。
🔥 Vibe Coding 核心 Prompt
【DP 問題詠唱範例】
「請幫我解決 0/1 背包問題：1. 有 N 個物品，每個物品有重量 w[i] 與價值 v[i]。2. 背包容量為 W。3. 請建立 DP 二維陣列 dp[i][w] 表示前 i 個物品在容量 w 時的最大價值。4. 推導遞迴關係式：dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]] + v[i])。5. 輸出最大價值與選取了哪些物品。6. 用 Vibe Coding 風格解釋為什麼這個遞迴式是正確的。」
🎯 課程大綱
- DP 核心思想：遞迴 + 記憶化
- 0/1 背包與完全背包
- 最長共同子序列 (LCS)
- 編輯距離 (Edit Distance)
- 實戰：自動拼寫檢查與推薦
課程導覽：這堂課你會學到什麼？
動態規劃（Dynamic Programming）是演算法設計中最重要也最常被面試的技巧之一。核心觀念是：把大問題拆成小問題，記錄小問題的答案，避免重複計算。
第一章：DP 核心思想
遞迴 + 記憶化（Memoization）。從 Fibonacci 數列開始，理解重疊子問題和最優子結構。
第二章：0/1 背包問題
經典的 NP-hard 問題——但在限制條件下可以用 DP 求出最佳解。理解狀態定義和狀態轉移。
第三章：最長共同子序列 LCS
字串比對的基礎。LCS 的 DP 表格是很多進階演算法的原型。
第四章：編輯距離（Levenshtein Distance）
拼寫檢查的核心——計算把一個字串轉換成另一個字串需要的最少操作次數。
第五章：拼寫檢查 API
把編輯距離包裝成 FastAPI 服務——輸入錯誤單字，回傳正確建議。