DP 問題的一般分析方法

以下均以 01 背包舉例。

狀态表示

将每一個狀态看作一個集合集的屬性。

\(f[i,j]\) 表示前 \(i\) 個物品中總體積為 \(j\) 的物品集合集的元素大小和的最大值（屬性）。

\(e.g.\)

\[id:1,2,3\]

\[w_i:4,5,9\]

\[v_i:6,8,7\]

\[f[3,9]\to\{\{1,2\},\{3\}\}\]

其中 \(\{1,2\}\) 的價值和最大，為 \(6+8=14\)，故 \(f[3,9]=14\)

常見的屬性有：大小、最值、和、乘積、異或和……

狀态轉移

對集合集中集合的劃分。

将 \(f[i,j]\) 的集合集劃分成包含 \(i\) 物品的集合和不包含 \(i\) 物品的集合。

兩種情況分别對應 \(f[i-1,j]\) 和 \(f[i-1,j-w_i]+v_i\)。

是以狀态轉移方程為 \(f[i,j]=\max(f[i-1,j],f[i-1,j-w_i]+v_i)\)。

\(e.g.\)

\[id:1,2,3,4\]

\[w_i:4,5,9,8\]

\[v_i:6,8,7,1\]

\[f[4,13]\to\{\color{blue}{\{1,3\}},\color{red}{\{2,4\}}\}\]

藍色為不含 \(i\) 的，紅色為含 \(i\) 的。

再思考，可以用滾動數組優化空間複雜度。