$1D/1D$動態規劃

形如$dp[i]=min\{dp[j]+w(j,i)\}(L_i\le j\le R_i)$ 的$dp$方程被稱作$1D/1D$動態規劃，其中$L_i$和$R_i$單調遞增，$w(j,i)$決定著優化策略選擇。

($dp[i]=max\{dp[j]+w(j,i)\}$與$dp[i]=min\{dp[j]+w(j,i)\}$類似，本文不贅述)

決策單調性優化DP

決策單調性

設$j_0[i]$表示$dp[i]$轉移的最優決策點，那么決策單調性可描述為 $?i\le j,j_0[i]\le j_0[j]$。也就是說隨著$i$的增大，所找到的最優決策點是遞增態（非嚴格遞增）。

四邊形不等式

表述1：
$w(x,y)$為定義在整數集合上的一個二元函數，若 $?a\le b\le c\le d,w(a,c)+w(b,d)\le w(a,d)+w(b,c)$，那么函數$w$滿足四邊形不等式。

表述2：
$w(x,y)$為定義在整數集合上的一個二元函數，若 $?a<b,w(a,b)+w(a+1,b+1)\le w(a+1,b)+w(a,b+1)$，那么函數$w$滿足四邊形不等式。

定理：

$1D/1D$動態規劃具有決策單調性當且僅當函數$w$滿足四邊形不等式 時成立。

實現

單調隊列優化DP

形如$dp[i]=min\{dp[j]+A(i)+B(j)\}$的$dp$方程均可嘗試使用單調隊列優化。

實現

斜率優化DP

形如$dp[i]=min\{A(i)\times B(j)+C(i)+D(j)\}$的$dp$方程可嘗試使用斜率優化。

1.0 $B(j)$嚴格單調遞增

法一：線性規劃

考慮把 $dp[i]=A(i)\times B(j)+C(i)+D(j)$ 化成$y=kx+b$的形式，其中$y,x$只與$j$有關，$k,b$只與$i$有關，且 $x$嚴格單調遞增。

則有：
$D(j)=?A(i)\times B(j)+dp[i]?C(i)$
其中$y=D(j),k=?A(i),x=B(j),b=dp[i]?C(i)$

在平面直角坐標系上把所有的$(x_j,y_j)$（即$(B(j),D(j))$）標出來。
要令$dp[i]$最小，則要令$b$最小，即是要找到某一點$(x_j,y_j)$，使斜率為$k$的直線經過該點時算出來的$b$最小。
發現只有 在給出點的下凸殼上的點可能成為最優決策點。

法二：代數法+數形結合

設$j_1,j_2$ $(0\le j_1<j_2<i)$ 為$dp[i]$的兩個決策點，且決策點$j_2$優于$j_1$，則有：
$A(i)\times B(j_2)+C(i)+D(j_2)\le A(i)\times B(j_1)+C(i)+D(j_1)$

化簡式子，使不等號左邊只與$i$有關，不等號右邊只與$j_1,j_2$有關：
$A(i)\le ?\frac{D(j_2)?D(j_1)}{B(j_2)?B(j_1)}$
$?A(i)\ge \frac{D(j_2)?D(j_1)}{B(j_2)?B(j_1)}$
設$x_j=B(j),y_j=D(j)$，則$\frac{D(j_2)?D(j_1)}{B(j_2)?B(j_1)}$可以看作$P_{j_1}(x_{j_1},y_{j_1})$,$P_{j_2}(x_{j_2},y_{j_2})$兩點連線的斜率。

也就是說，如果存在兩個決策點$j_1,j_2$滿足$0\le j_1<j_2<i$，使得$P_{j_1}$,$P_{j_2}$兩點連線的斜率$\le ?A(i)$，那么決策點$j_2$優于$j_1$。

于是，對于這樣子的三個點，可證$B$一定不是最優決策點。

我們可以將$B$從候選決策點中踢出去（刪除），只留下$A$和$C$，刪后的情況如下圖所示：

最終，我們維護的候選決策點應該構成了一個下凸殼：

實現

進一步優化

若$k_0(i)=?A(i),B(j)$均單調不減，則該$dp$方程必定有決策單調性。那么就不需要在凸殼上二分找最優決策點了。

總結

以上是生活随笔為你收集整理的1D/1D动态规划的三种优化方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。