🧩 動態規劃實戰
動態規劃 (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)
- 實戰：自動拼寫檢查與推薦