#knapsack

Stanford CS161 Lecture 13：從 LCS、背包到樹上獨立集的動態規劃設計法

Lecture 13 把動態規劃整理成五步：選 state、寫 transition、填表、回復解、再優化實作。LCS 是 O(mn)，兩種背包都是 O(nW) 的擬多項式時間，樹上最大權重獨立集則能在 O(|V|) 完成。