樹形動(dòng)態(tài)規(guī)劃是在屬性結(jié)構(gòu)上實(shí)現(xiàn)的動(dòng)態(tài)規(guī)劃，也稱樹形DP。動(dòng)態(tài)規(guī)劃自身是多階段決策問題，而樹形結(jié)構(gòu)有明顯的層次性，正好對(duì)應(yīng)動(dòng)態(tài)規(guī)劃的多個(gè)階段。樹形結(jié)構(gòu)有明顯的層次性，正好對(duì)應(yīng)動(dòng)態(tài)規(guī)劃的多個(gè)階段。樹形DP的求解過程一般為自底向上，將子樹從小到大作為DP的“階段”，將節(jié)點(diǎn)編號(hào)作為DP狀態(tài)的第1維，代表以該節(jié)點(diǎn)為根的子樹。樹形DP一般采用深度優(yōu)先遍歷的方法，遞歸求解每顆子樹，回溯時(shí)從子節(jié)點(diǎn)向上進(jìn)行狀態(tài)轉(zhuǎn)移。在當(dāng)前節(jié)點(diǎn)的所有子樹都求解完畢后，才可以求解當(dāng)前節(jié)點(diǎn)。
樹形DP有兩種（大部分情況不可以相互轉(zhuǎn)化）：
- 根到葉子：不過這種動(dòng)態(tài)規(guī)劃在實(shí)際的問題中運(yùn)用的不多。
- 葉子到根：根的子節(jié)點(diǎn)傳遞有用的信息給根，完后根得出最優(yōu)解的過程。
葉子到根節(jié)點(diǎn)
每個(gè)節(jié)點(diǎn)上均有一盞燈和三個(gè)開關(guān)。節(jié)點(diǎn)值為 0 表示燈處于「關(guān)閉」?fàn)顟B(tài)，節(jié)點(diǎn)值為 1 表示燈處于「開啟」?fàn)顟B(tài)。每個(gè)節(jié)點(diǎn)上的三個(gè)開關(guān)各自功能如下：
- 開關(guān) 1：切換當(dāng)前節(jié)點(diǎn)的燈的狀態(tài)；
- 開關(guān) 2：切換以當(dāng)前節(jié)點(diǎn)為根的子樹中，所有節(jié)點(diǎn)上的燈的狀態(tài)；
- 開關(guān) 3：切換當(dāng)前節(jié)點(diǎn)及其左右子節(jié)點(diǎn)（若存在的話）上的燈的狀態(tài)；
需要找到最少的開關(guān)更新次數(shù)。
求解過程：用長度為2的二進(jìn)制數(shù)來表示樹的狀態(tài)，低位表示根節(jié)點(diǎn)，高位表示除根以外的節(jié)點(diǎn)，其中00為全關(guān)，01為根節(jié)點(diǎn)開、其他全關(guān)，10為根節(jié)點(diǎn)關(guān)、其他全開，11為全開。用長度為3的二進(jìn)制數(shù)來表示操作狀態(tài)，從低位到高位分別表示操作1、2、3，一共8種狀態(tài)。其執(zhí)行操作后轉(zhuǎn)移的條件為左右子樹同時(shí)滿足全開或者全關(guān)。
使用二進(jìn)制進(jìn)行狀態(tài)壓縮的好處是切換開關(guān)狀態(tài)只需要使用異或。
