DP（動态規劃）總結

2023-03-19 01:14:50

前言

動态規劃是很重要的一個知識點，大大小小的比賽總會有一兩道DP題，足以說明動态規劃的重要性。

動态規劃主要是思想，并沒有固定的模闆，那麼，怎麼判斷題目是不是動态規劃呢？

DP題一般都會滿足三個條件：子問題重疊、無後效性、最優子結構性質。

動态規劃把原問題看作若幹個重疊子問題，每個子問題的求解過程都是一個階段，

動态規劃要求目前階段不會被後續階段影響（即已經解決的子問題不被後續子問題影響），這便是無後效性。

一般情況下，動态規劃在解決最優問題時，每個階段的最優解應該由前面階段的最優解導出，這便是最優子結構性質。

知道題目是動态規劃後，怎麼解決呢？

解決動态規劃問題，重點在于狀态與狀态轉移方程：

顧名思義，狀态通常指某種情況下目标的某種情況，要注意邊界；

狀态轉移方程指把目前階段的狀态轉移到下一個階段的狀态的方程。

狀态與狀态轉移方程因題而異，想要熟練的定義出狀态、得出狀态轉移方程，最主要的方法便是多刷題，DP題做多了自然就知道如何定義了。

具體的各類DP與題目如下。