定義一組子問題，按照由小到大慌植，以小問題的解答支持大問題求解的模式蝶柿，依次解決所有的子問題交汤，并最終得到原問題的解答芙扎。
隱含思想
DAG有向無圈圖的拓?fù)渑判?/p>
節(jié)點(diǎn)對應(yīng)于我們定義的子問題，邊表示子問題間的依賴關(guān)系：即如果求解子問題B必須依賴子問題A的解答圈浇，則（概念上）存在一條由A到B的邊磷蜀。
子問題性質(zhì)
存在子問題間的一種排序以及如下的關(guān)聯(lián)關(guān)系：對于任意一個(gè) 子問題，這種關(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個(gè)節(jié)點(diǎn)耙册，則最終子問題數(shù)量為O(nlogn)详拙。
最長遞增子序列
輸入：一個(gè)數(shù)字序列a1蹲诀、a2脯爪、...尚揣、an。
輸出：從以上序列中按順序選出的一個(gè)子集滨巴，并且嚴(yán)格單調(diào)遞增，形如a(i1)熄守、a(i2)裕照、a(ik)，其中1<=i1<i2<...<ik<=n负间。
策略1
為每個(gè)元素建立一個(gè)對應(yīng)的節(jié)點(diǎn)态秧，對任意兩個(gè)存在遞進(jìn)關(guān)系的元素ai和ak（即同時(shí)滿足i<j且ai<ak）愤诱，增加一條連接兩者對應(yīng)節(jié)點(diǎn)的有向邊(i, j)
形成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)
- 為方便圖的鄰接表表示砌溺，可變形為
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
- 求反轉(zhuǎn)圖G的鄰接表表示
此時(shí)無需構(gòu)造原圖G
時(shí)間復(fù)雜度max{O(n^2), O(V+E)}
策略2
子問題：將LCS(i)記做包含的最長遞增子序列長度鲜棠。
LIS[i] = max{1,LIS[k]+1}培慌，其中吵护，對于任意的k<=i-1，arr[i] > arr[k]雄坪。
最長公共子序列LCS
輸入：兩個(gè)序列X)笨农，Y)。
輸出：一個(gè)序列S任意刪除若干個(gè)字符得到新序列T，則T叫做S的子序列孕豹。兩個(gè)序列X和Y的公共子序列中十气，長度最長的那個(gè)，定義為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})
時(shí)間復(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})
在上述過程中記錄)的最大值宏胯，最后即可得到最長公共子串的長度
時(shí)間復(fù)雜度O(n^2)
最長公共子串類似：最大子串和
PAT1007. Maximum Subsequence Sum
輸入：給定一個(gè)序列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)前子串左邊開始位置）。最后即可得到最大子串和以及最大子串牲芋。
時(shí)間復(fù)雜度O(n)
空間復(fù)雜度O(1)
算法過程中只需存儲上一步的Sum和位置信息
變體2：最長遞增子序列LIS
- 對輸入序列X進(jìn)行排序，得到序列Y
- 求解序列X和Y的最長公共子序列捺球，即是序列X的最長遞增子序列
時(shí)間復(fù)雜度O(n^2)
編輯距離
隨意插入空隙“-”到每個(gè)字符串中使兩個(gè)字符串對齊缸浦，對于該種對齊方式，代價(jià)為兩個(gè)字符串對應(yīng)字母不相同的列數(shù)氮兵。如：
S - N O W Y
S U N N - Y
SNOWY和SUNNY該種對齊方式的代價(jià)為3
編輯距離是指兩個(gè)字符串的各種對齊所可能具有的最小代價(jià)裂逐。
策略
子問題：定義E(i, j)為尋找兩個(gè)字符串x[1...i]與y[1...j]之間的編輯距離。
由于要將E(i, j)表示為較之更小的子問題的表達(dá)式泣栈，我們考慮x[1...i]與y[1...j]所有對齊中最右側(cè)的列的可能情況:
- x[i]與-
- -與y[j]
- 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]時(shí)，diff()取0南片；否則取1
所有子問題E(i, j)的解構(gòu)成一個(gè)二維表篙悯，要保證求解順序（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
時(shí)間復(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，價(jià)值v1,v2,...,vn峡谊。背包最多能裝W磅茫虽，如何組合才能使背包攜帶的價(jià)值最高既们。
廣泛應(yīng)用于需要機(jī)遇有限資源進(jìn)行選擇判斷的領(lǐng)域
多副本的背包問題
每種物品的數(shù)量無限
1. 子問題：考慮容量較小的背包
定義K(w) = 容量w可以容納的最高價(jià)值
若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)
時(shí)間復(fù)雜度O(nW)
see implement: dp.bag.MultiBagProWithCapa
構(gòu)造DAG
針對每個(gè)w構(gòu)造節(jié)點(diǎn)，其中w in 0~W斯棒。對于每個(gè)節(jié)點(diǎn)與每個(gè)物品盾致，使用該物品的容量確定邊的終點(diǎn)，使用該物品的價(jià)值確定邊的權(quán)值荣暮，可以構(gòu)造出一個(gè)DAG庭惜。求背包所能容納的最高價(jià)值最終歸結(jié)為尋找該DAG的最長路徑。
2. 子問題：考慮較少的物品種類
TODO
單副本的背包問題
每種物品都只有一件
策略
在K(w)子問題中包含關(guān)于哪件物品已經(jīng)被使用過的信息穗酥。
定義子問題K(w, j) = 基于背包容量w和物品1, ..., j所能得到的最高價(jià)值
用更小的子問題表示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)}
時(shí)間復(fù)雜度O(nW)
see implement: dp.bag.SingleBagPro
矩陣鏈?zhǔn)较喑?/h5>
一個(gè)mn的矩陣與一個(gè)np的矩陣相乘护赊，約需要進(jìn)行mnp次乘法。通過在矩陣鏈?zhǔn)较喑斯降牟煌恢貌迦肜ɑ∶陨龋覀兛梢缘玫胶芏嗖煌挠?jì)算方式百揭，那么哪種乘法次序代價(jià)最兴ァ蜓席？
自然的表示
滿二叉樹：每個(gè)矩陣對應(yīng)一個(gè)葉節(jié)點(diǎn)，樹根為最終的乘積课锌，而樹的內(nèi)部節(jié)點(diǎn)表示中間過程的部分乘積厨内。各種可能的乘法次序?qū)?yīng)不同的滿二叉樹。
如果一個(gè)樹最優(yōu)渺贤，那么其子樹必然也最優(yōu)
策略
假設(shè)我們需要計(jì)算
定義 = the ; minimum ; cost ; of ; computing A_iA_{i+1}...A_j)
C(i, j)可分割為C(i, k)和C(k+1, j)兩個(gè)子問題雏胃，即
 = 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)求解到某個(gè)子問題時(shí)志鞍，比該子問題規(guī)模小的子問題已被求解。
因?yàn)?i,j)坐標(biāo)并不在(i+1, j)坐標(biāo)的下邊或右邊固棚，此時(shí)無法按照從上至下仙蚜，從左至右的求解順序
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
時(shí)間復(fù)雜度O(n^3)
動態(tài)規(guī)劃 VS 遞歸記憶
記憶：遞歸算法記住之前的調(diào)用結(jié)果
- 優(yōu)點(diǎn)：記憶只會求解那些實(shí)際被用到的子問題
- 缺點(diǎn)：遞歸所具有的的間接開銷通常較高厂汗，其大O符號所包含的常數(shù)因子相對而言較大
寫在最后
- 立個(gè)Flag，
TODOwill be done some day娶桦。 - 渣代碼，且輕噴?:worried:?衷畦。
