把算過的存起來,避免重複計算。大問題由小問題的答案疊出來。
最佳子結構 —— 大問題的答案,可以由子問題的答案組合出來(例如 dp[i] 由 dp[i-1] 來)。
重疊子問題 —— 同樣的子問題會被重複用到很多次(這時存起來才划算)。
少了重疊就沒必要 DP —— 分治的子問題不重疊,存了也沒用。
關鍵是「狀態」和「轉移式」 —— 定義 dp[i] 代表什麼、以及它怎麼從更小的算出來。
由上而下・記憶化(top-down) —— 照遞迴的樣子寫,但把算過的存進 cache;遇到算過的直接拿。最貼近原本的遞迴思路。
由下而上・填表(bottom-up) —— 從最小的子問題開始,一格格把表填滿,最後一格就是答案。沒有遞迴開銷。
兩者等價 —— 通常時間複雜度一樣,填表常更省記憶體(可只留最近幾格)。
下面視覺化就是「填表」 —— 從 dp[0] 一路填到 dp[n]。
1. 定義狀態 —— dp[i](或 dp[i][j])代表什麼?
2. 找轉移式 —— dp[i] 怎麼從更小的狀態算出來?(最難、最關鍵)
3. 定 base case —— 最小的子問題答案是什麼?
4. 決定順序 —— 要先算好誰,才能算 dp[i]?通常由小到大填。
到第 n 階的走法 = 到 n-1 階 + 到 n-2 階的走法,從下面一階階疊上來。
算過的答案抄在本子上,下次要用直接翻,絕不重算。
先蓋好低樓層,高樓層才有地基;由下往上一層層蓋,不能跳。
爬 8 階,每次可爬 1 或 2 階,問有幾種走法?狀態 dp[i] = 到第 i 階的走法數,轉移式 dp[i] = dp[i-1] + dp[i-2](最後一步爬 1 階或 2 階)。紫色是正在填的格、琥珀是它相加的兩格、綠色是填好的。按「下一步」由下而上填。
從費式的三種寫法、爬樓梯,到零錢兌換、背包、LIS、LCS、編輯距離、Kadane、打家劫舍。
❌ 沒有重疊子問題還硬用 DP —— 子問題不重複(如純分治),存了也沒省到。
❌ 狀態定義不清 —— dp[i] 到底代表什麼講不清,轉移式就寫不對。DP 一切從「定義狀態」開始。
❌ base case / 邊界錯 —— dp[0]、第一行第一列常要特別設,錯了整張表全歪。
❌ 填表順序錯 —— 算 dp[i] 時它依賴的格子還沒算好,要先確定依賴關係。
dp[i]=dp[i-1]+dp[i-2] 填表算給我看。(用視覺化對)O(2ⁿ),加了記憶化變 O(n)。省下來的到底是什麼?把答案打到對話裡,我幫你對。