????具有線性階段劃分的動態(tài)規(guī)劃算法統(tǒng)稱為線性動態(tài)規(guī)劃（簡稱線性 DP）。如果狀態(tài)包含多個(gè)維度，每個(gè)維度都是線性變化的階段，也稱為線性 DP。

????

????在樹形結(jié)構(gòu)上（非線性結(jié)構(gòu)）實(shí)現(xiàn)的動態(tài)規(guī)劃稱為樹形DP。

????動態(tài)規(guī)劃本身是多階段決策問題，而樹形結(jié)構(gòu)具有明顯的層次性，正好對應(yīng)動態(tài)規(guī)劃的多階段性。樹形DP一般自底向上，將子樹從小到大的順序作為 DP的 “階段”，將結(jié)點(diǎn)編號作為DP狀態(tài)的第一維，代表以該結(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)。