動態規劃題解

設$dp(pa,x)$表示你有$x$個東西可以分割
但是分割出來的最元素不會超過$pa$
而數字$n$的所有分割的答案就會是$dp(n,n)$

舉例來說，$dp(5,7)=13$，這13種分法如下：

5 2
5 1 1
-------------
4 3
4 2 1
4 1 1 1
-------------
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
-------------
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
-------------
1 1 1 1 1 1 1

$dp(5,2)=2$

2
1 1

$dp(4,3)=3$

3
2 1
1 1 1

$dp(3,4)=4$

3 1
2 2
2 1 1
1 1 1 1

$dp(2,5)=3$

2 2 1
2 1 1 1
1 1 1 1 1

$dp(1,6)=1$

1 1 1 1 1 1

根據觀察，可以得到以下的狀態轉移式
$$dp(pa,x)=\sum_{i=0}^{min(pa,x)} dp(i,x-i)$$

我們的目標是要把$A[0 \sim x]$以最小費用修改成$B[0 \sim y]$

插入可以想成先把$A[0 \sim x]$以最小費用修改成$B[0 \sim y-1]$
之後在尾端插入$B[y]$

因此插入的最小代價為$dp(x,y-1)+c0$

我們的目標是要把$A[0 \sim x]$以最小費用修改成$B[0 \sim y]$

刪除可以想成先把$A[0 \sim x]$刪除尾端元素成$A[0 \sim x-1]$後
在把刪除後的結果以最小費用修改成$B[0 \sim y]$

因此刪除的最小代價為$c1+dp(x-1,y)$

我們的目標是要把$A[0 \sim x]$以最小費用修改成$B[0 \sim y]$

修改可以想成先把$A[0 \sim x-1]$以最小費用修改成$B[0 \sim y-1]$
再把$A[x]$修改成$B[y]$

因此修改的最小代價為$dp(x-1,y-1)+c2$

$$ dp(x,y)=\left\{ \begin{array}{} dp(x-1,y-1) & & {A[x]==b[y]}\\ min\left( \begin{array}{rcl} dp(x,y-1)+c0 \\ c1+dp(x-1,y) \\ dp(x-1,y-1)+c2 \end{array} \right) & & {A[x]!=b[y]} \end{array} \right. $$

令$ A=abcbbbbba\\ B=abbbcbbac\\ C=acbbbbbba $
很明顯的其LCS只有一個為$abbbbba$

但我們可以把$B$的最尾端元素去掉
令$B^{'}=abbbcbba$
則$A,B^{'},C$的LCS同樣是$abbbbba$

$$ dp(x,y,z)=\left\{ \begin{array}{} dp(x-1,y-1,z-1)+1 & & {A[x]==b[y]==C[z]}\\ max\left( \begin{array}{rcl} dp(x-1,y,z) \\ dp(x,y-1,z) \\ dp(x,y,z-1) \end{array} \right) & & {else} \end{array} \right. $$

$let \; S^{'}=S-\{x\}$
$dp(x,S)=min(\{dp(u,S^{'})+dis(u,x):u \in S^{'}\})$

紅色部分是原本字串的其中一個最長迴文子序列
aacdaab

$$ dp(l,r)=\left\{ \begin{array}{} dp(l+1,r-1) & & {S[l]==S[r]}\\ min\left( \begin{array}{rcl} dp(l+1,r)\\ dp(l,r-1) \end{array} \right)+1 & & {S[l]!=S[r]} \end{array} \right. $$