定義一組子問題，按照由小到大，以小問題的解答支持大問題求解的模式，依次解決所有的子問題，并最終得到原問題的解答。

隱含思想

DAG有向無圈圖的拓?fù)渑判?/p>

節(jié)點(diǎn)對應(yīng)于我們定義的子問題，邊表示子問題間的依賴關(guān)系：即如果求解子問題B必須依賴子問題A的解答，則（概念上）存在一條由A到B的邊。

子問題性質(zhì)
存在子問題間的一種排序以及如下的關(guān)聯(lián)關(guān)系：對于任意一個 子問題，這種關(guān)聯(lián)關(guān)系說明了如何在給定（在排序中）相對其“較小”的子問題的解的前提下，求得該子問題的解

妙處
恰當(dāng)?shù)剡x擇子問題，使得所有重要的信息都得以保存并便于今后使用

常見子問題模式

模式1

輸入為x1, x2, ..., xn，子問題為x1, x2, ..., xi。

最終子問題數(shù)量將為線性。

模式2

輸入為x1, x2, ..., xn和y1, y2, ..., ym，子問題為x1, x2, ..., xi和y1, y2, ..., yj。

最終子問題數(shù)量為O(m*n)

模式3

輸入為x1, x2, ..., xn，子問題為xi, x(i+1), ..., xj。

最終子問題數(shù)量為O(n^2)。

模式4

輸入為樹，子問題為其子樹。

若樹有n個節(jié)點(diǎn)，則最終子問題數(shù)量為O(nlogn)。

最長遞增子序列

輸入：一個數(shù)字序列a1、a2、...、an。

輸出：從以上序列中按順序選出的一個子集，并且嚴(yán)格單調(diào)遞增，形如a(i1)、a(i2)、a(ik)，其中1<=i1<i2<...<ik<=n。

策略1

1. 為每個元素建立一個對應(yīng)的節(jié)點(diǎn)，對任意兩個存在遞進(jìn)關(guān)系的元素ai和ak（即同時滿足i<j且ai<ak），增加一條連接兩者對應(yīng)節(jié)點(diǎn)的有向邊(i, j)

2. 形成dag，求遞增子序列問題變?yōu)閷ふ襠ag中的最長路徑

for j = 1,2,...,n:
    L(j) = 1 + max{L(i):(i, j) in E}
return max{L(j)}

L(j)是以序列中j為終點(diǎn)的最長路徑，即對應(yīng)于最長遞增子序列的長度

實(shí)現(xiàn)

1. 為方便圖的鄰接表表示，可變形為

for i = 1,2,...,n:
    for (i, j) in E:
    L(j) = max {L(j), L(i) + 1}
return max{L(j)}

see implement: dp.LongestIncreSub

2. 求反轉(zhuǎn)圖G的鄰接表表示

此時無需構(gòu)造原圖G

時間復(fù)雜度max{O(n^2), O(V+E)}

策略2

的最長遞增子序列長度。

LIS[i] = max{1,LIS[k]+1}，其中，對于任意的k<=i-1，arr[i] > arr[k]。

最長公共子序列LCS

輸入：兩個序列X)，Y)。

輸出：一個序列S任意刪除若干個字符得到新序列T，則T叫做S的子序列。兩個序列X和Y的公共子序列中，長度最長的那個，定義為X和Y的最長公共子序列。

策略
子問題：將LCS(i, j)記做)與)的最長公共子序列長度。

考察

即
=\begin{cases}0 & if ; i=0 ; or ; j=0\LCS(i-1, j-1)+1 & if ; i>0, j>0, and ; x_i = x_j\max {LCS(i-1, j), LCS(i, j-1)} & if ; i>0, j>0, and x_i != x_j\end{cases})

時間復(fù)雜度max{O(n^2)}

變體1：最長公共子串

子序列不要求子序列中的字符在原序列中連續(xù)，而子串要求連續(xù)。

策略
子問題：)表示以

考察

即
=\begin{cases}0 & if;i=0;or;j=0\L(i-1, j-1)+1 & if;i>0, j>0, and ; x_i = x_j\0 & if ; i>0, j>0, and x_i != x_j\end{cases})

在上述過程中記錄)的最大值，最后即可得到最長公共子串的長度

時間復(fù)雜度O(n^2)

最長公共子串類似：最大子串和

PAT1007. Maximum Subsequence Sum

輸入：給定一個序列X)。

輸出：找出該序列具有最大和的子串。如果該序列所有數(shù)均為負(fù)數(shù)，則輸出0。

策略
子問題：

考察

即
=\begin{cases}x_i & if ; i=0 ; or ; Sum(i-1)<=0\x_i + Sum(i-1) & if ; Sum(i-1)>0\end{cases})

的最大值，并根據(jù)第一種情況重新修改tempLeft（當(dāng)前子串左邊開始位置）。最后即可得到最大子串和以及最大子串。

時間復(fù)雜度O(n)

空間復(fù)雜度O(1)

算法過程中只需存儲上一步的Sum和位置信息

變體2：最長遞增子序列LIS

1. 對輸入序列X進(jìn)行排序，得到序列Y
2. 求解序列X和Y的最長公共子序列，即是序列X的最長遞增子序列

時間復(fù)雜度O(n^2)

編輯距離

隨意插入空隙“-”到每個字符串中使兩個字符串對齊，對于該種對齊方式，代價為兩個字符串對應(yīng)字母不相同的列數(shù)。如：

S - N O W Y
S U N N - Y

SNOWY和SUNNY該種對齊方式的代價為3

編輯距離是指兩個字符串的各種對齊所可能具有的最小代價。

策略
子問題：定義E(i, j)為尋找兩個字符串x[1...i]與y[1...j]之間的編輯距離。
由于要將E(i, j)表示為較之更小的子問題的表達(dá)式，我們考慮x[1...i]與y[1...j]所有對齊中最右側(cè)的列的可能情況:

1. x[i]與-
2. -與y[j]
3. x[i]與y[j]
   因此，E(i, j) = min{1+E(i-1, j), 1+E(i, j-1), diff(x[i], y[j])+E(i-1, j-1)}

當(dāng)x[i]=y[j]時，diff()取0；否則取1

所有子問題E(i, j)的解構(gòu)成一個二維表，要保證求解順序（E(i-1, j), E(i, j-1)和E(i-1, j-1)總是在E(i, j)之前求解）

算法如下：

for i = 0, 1, 2 ... m:
    E(i, 0) = i
for j = 1, 2 ... n:
    E(0, j) = j
for i = 1, 2 ... m:
    for j = 1, 2 ... n:
        E(i, j) = min{E(i-1, j)+1, E(i, j-1)+1, E(i-1, j-1)+diff(i,j)}
return E(m, n)

see implement: dp.EditingDistance
時間復(fù)雜度為O(m*n)

擴(kuò)展
在二維表中，令{(i-1, j-1)->(i, j) : x[i]=y[j]}中邊的長度置為0，并將其他所有邊的長度置為1。則求編輯距離問題變?yōu)榍骴ag中的最短路徑，即點(diǎn){0,0}與{m,n}之間的最短路徑。

在該路徑上，向下的移動表示刪除，向右為插入，而對角線移動表示匹配或者替換。

背包問題

一共有n件物品，分別重w1,w2, ..., wn，價值v1,v2,...,vn。背包最多能裝W磅，如何組合才能使背包攜帶的價值最高。

廣泛應(yīng)用于需要機(jī)遇有限資源進(jìn)行選擇判斷的領(lǐng)域

多副本的背包問題

每種物品的數(shù)量無限
1. 子問題：考慮容量較小的背包
定義K(w) = 容量w可以容納的最高價值
若K(w)的最優(yōu)解包含物品i，將物品i去掉，則會留下K(w-wi)的最優(yōu)解。不知道包含哪些i，因此嘗試所有的可能
 = max_{i:w_i<=w} {K(w-w_i)+v_i})

K(0) = 0
for w = 1 to W:
    K(w)= max{K(w-w(i))+v(i):wi<=w}
return K(W)

時間復(fù)雜度O(nW)

see implement: dp.bag.MultiBagProWithCapa

構(gòu)造DAG
針對每個w構(gòu)造節(jié)點(diǎn)，其中w in 0~W。對于每個節(jié)點(diǎn)與每個物品，使用該物品的容量確定邊的終點(diǎn)，使用該物品的價值確定邊的權(quán)值，可以構(gòu)造出一個DAG。求背包所能容納的最高價值最終歸結(jié)為尋找該DAG的最長路徑。

2. 子問題：考慮較少的物品種類
TODO

單副本的背包問題

每種物品都只有一件
策略
在K(w)子問題中包含關(guān)于哪件物品已經(jīng)被使用過的信息。
定義子問題K(w, j) = 基于背包容量w和物品1, ..., j所能得到的最高價值
用更小的子問題表示K(w, j)：
 = max(K(w-w_j,j-1)+v_j, K(w, j-1)))

initialize all K(0, j) = 0 and all K(w, 0) = 0
for j = 1 to n:
    for w = 1 to W:
        if w(j) > w: K(w, j) = K(w, j-1)
        else: K(w, j) = max{K(w, j-1), K(w-w(j), j-1)+v(j)}

時間復(fù)雜度O(nW)

see implement: dp.bag.SingleBagPro

矩陣鏈?zhǔn)较喑?/h5>

一個mn的矩陣與一個np的矩陣相乘，約需要進(jìn)行mnp次乘法。通過在矩陣鏈?zhǔn)较喑斯降牟煌恢貌迦肜ɑ?，我們可以得到很多不同的?jì)算方式，那么哪種乘法次序代價最??？
自然的表示
滿二叉樹：每個矩陣對應(yīng)一個葉節(jié)點(diǎn)，樹根為最終的乘積，而樹的內(nèi)部節(jié)點(diǎn)表示中間過程的部分乘積。各種可能的乘法次序?qū)?yīng)不同的滿二叉樹。

如果一個樹最優(yōu)，那么其子樹必然也最優(yōu)

策略
假設(shè)我們需要計(jì)算

其中每個矩陣的維數(shù)分別為
定義 = the ; minimum ; cost ; of ; computing A_iA_{i+1}...A_j)
C(i, j)可分割為C(i, k)和C(k+1, j)兩個子問題，即
 = min_{i<=k<j}[C(i,k) + C(k+1, j) + m_{i-1}m_km_j]?)

由于C(i, k)的維數(shù)為

，C(k+1, j)的維數(shù)為

求解順序：當(dāng)求解到某個子問題時，比該子問題規(guī)模小的子問題已被求解。

因?yàn)?i,j)坐標(biāo)并不在(i+1, j)坐標(biāo)的下邊或右邊，此時無法按照從上至下，從左至右的求解順序

for i = 1 to n: C(i, i) = 0
for s = 1 to n-1:
    for i = 1 to n-s:
        j = i+s
        C(i, j) = min{C(i,k) + C(k+1, j) + m(i-1)*m(k)*m(j):i<=k<j}
return C(1, n)

see implement: dp.MatrixChain

時間復(fù)雜度O(n^3)

動態(tài)規(guī)劃 VS 遞歸記憶

記憶：遞歸算法記住之前的調(diào)用結(jié)果

• 優(yōu)點(diǎn)：記憶只會求解那些實(shí)際被用到的子問題
• 缺點(diǎn)：遞歸所具有的的間接開銷通常較高，其大O符號所包含的常數(shù)因子相對而言較大

寫在最后

• 立個Flag，TODO will be done some day。
• 渣代碼，且輕噴?:worried:?。