假設(shè)你面前有一棟n層的大樓和m個(gè)雞蛋驼鞭，假設(shè)將雞蛋從f層或更高的地方放扔下去，雞蛋才會(huì)碎尺碰，否則就不會(huì)挣棕。你需要設(shè)計(jì)一種策略來(lái)確定f的值汇竭，求最壞情況下扔雞蛋次數(shù)的最小值。
乍一看這道題很抽象穴张，可能有的人一看到這個(gè)題目從來(lái)沒(méi)做過(guò)，就懵逼了两曼。其實(shí)不用慌張皂甘，再花里胡哨的題目，最后都可以抽象成我們熟悉的數(shù)據(jù)結(jié)構(gòu)和算法去解決悼凑。
不限雞蛋
首先偿枕，我們從一個(gè)簡(jiǎn)單的版本開始理解，假如不限制雞蛋個(gè)數(shù)户辫，即把題目改成n層大樓和無(wú)限個(gè)雞蛋渐夸。那么這題要怎么解呢？
第一步就是要充分理解題意渔欢，排除題目中的干擾墓塌，建立模型：
在一棟n層的大樓中尋找目標(biāo)樓層f --> 其實(shí)就是在一個(gè)1～n的數(shù)組中查找一個(gè)目標(biāo)數(shù)字。
雞蛋碎了就代表樓層過(guò)高奥额，否則就代表樓層過(guò)低 --> 每次嘗試都能知道當(dāng)前數(shù)字是大了還是小了苫幢。
很顯然，這就是一個(gè)二分查找能解決的問(wèn)題垫挨。
扔雞蛋的次數(shù)就是二分查找的比較次數(shù)韩肝，即$log_2(n+1)$。
限制雞蛋個(gè)數(shù)
那我們現(xiàn)在再來(lái)看限制雞蛋個(gè)數(shù)情況下九榔，肯定沒(méi)法用二分查找哀峻，但是由于求解的是一個(gè)最優(yōu)值，我們自然而然地想到了動(dòng)態(tài)規(guī)劃哲泊。
四步走
動(dòng)態(tài)規(guī)劃的題目剩蟀，這邊提供一個(gè)思路，就是四步走：
問(wèn)題建模攻旦，優(yōu)化的目標(biāo)函數(shù)是什么喻旷？約束條件是什么？
劃分子問(wèn)題（狀態(tài)）
列出狀態(tài)轉(zhuǎn)移方程及初值
是否滿足最優(yōu)子結(jié)構(gòu)性質(zhì)
建模
這一步非常非常重要牢屋，它建立在良好地理解題意的基礎(chǔ)上且预。其實(shí)很多動(dòng)態(tài)規(guī)劃的題目都有這樣的特點(diǎn)：
目標(biāo)是求一個(gè)最優(yōu)值
每一步?jīng)Q策有代價(jià)，總代價(jià)有一個(gè)約束值烙无。
而這道題：
目標(biāo)函數(shù)f(n)：代表在1～n的樓層中找到f層的嘗試次數(shù)锋谐，我們的目標(biāo)就是求出f(n)的最優(yōu)值。
每一步?jīng)Q策的代價(jià)：雞蛋可能會(huì)碎截酷；總代價(jià)的約束值：雞蛋總個(gè)數(shù)涮拗。
劃分子問(wèn)題
我們知道動(dòng)態(tài)規(guī)劃就是多階段決策的過(guò)程，最后求解組合最優(yōu)值爷辱。
我們先舉一個(gè)簡(jiǎn)單例子稽莉，來(lái)理解劃分子問(wèn)題的思路彬檀，看下面這張圖:
問(wèn)題：求起點(diǎn)集 S1～S5到終點(diǎn)集 T1～T5的最短路徑霍骄。
分析這道題：定義子問(wèn)題dis[i]代表節(jié)點(diǎn)i到終點(diǎn)的最短距離昏翰，沒(méi)有約束條件盆佣。
然后問(wèn)題劃分為4個(gè)階段：
階段1求出離終點(diǎn)最近的C1~C4節(jié)點(diǎn)到終點(diǎn)的最短路徑dis[C1]~dis[C4]隶糕。
階段2求出離終點(diǎn)最近的B2~B5節(jié)點(diǎn)到終點(diǎn)的最短路徑dis[B1]~dis[B5]尚揣，需要建立在階段1的結(jié)果上計(jì)算抑堡。例如B2節(jié)點(diǎn)到終點(diǎn)有兩條路摆出，B2～C1，B2～C2首妖，dis[C1]=2偎漫，B2到C1的長(zhǎng)度=3；而dis[C2]=3有缆，B2到C2的長(zhǎng)度=6象踊，因此dis[B2]=3+dis[B1]=5。
階段3和階段4也是以此類推妒貌，最終就求出得到dis[S1]~dis[S5]通危，得出最小路徑為圖中紅色的兩條。
在這道題中灌曙，dis[i]就是劃分出來(lái)的子問(wèn)題菊碟，每一步?jīng)Q策都是一個(gè)子問(wèn)題，而且每一個(gè)子問(wèn)題都依賴于以前子問(wèn)題的計(jì)算結(jié)果在刺。
因此逆害，在動(dòng)態(tài)規(guī)劃中，定義一個(gè)合理的子問(wèn)題非常重要蚣驼。
而扔雞蛋這道題比上面這道題多了個(gè)約束條件魄幕，我們把子問(wèn)題定義為：用i個(gè)雞蛋，在j層樓上扔颖杏，在最壞情況下確定目標(biāo)樓層E的最少次數(shù)纯陨，記為狀態(tài)f[i,j]。
列出狀態(tài)轉(zhuǎn)移方程和初值
假如決策是在第k層扔下雞蛋留储，有兩種結(jié)果：
雞蛋碎了翼抠，此時(shí)e<k，我們只能用i-1個(gè)蛋在下面的j-1層繼續(xù)尋找e获讳。并且要求最壞情況下的次數(shù)最少阴颖，這是一個(gè)子問(wèn)題，答案為f[i-1,j-1]丐膝，總次數(shù)便是f[i-1,j-1]+1量愧。
雞蛋沒(méi)碎钾菊，此時(shí)e>=k，我們繼續(xù)用這i個(gè)蛋在上面的j-k層尋找E偎肃。注意：在k～j層尋找和在1～(j-k)層尋找沒(méi)有區(qū)別煞烫，因?yàn)椴襟E都是一樣的，只不過(guò)這(j-k)層在上面罷了累颂，所以就把它看成是對(duì)1～(j-k)層的操作红竭。因此答案為f[i,j-k]，次數(shù)為f[i,j-k]+1喘落。
初值：
當(dāng)層數(shù)為0時(shí)，f[i,0]=0最冰，當(dāng)雞蛋個(gè)數(shù)為1時(shí)瘦棋，只能從下往上一層層扔，f[1,j]=j暖哨。
因?yàn)槭且顗那闆r赌朋，所以這兩種情況要取大值：max{f[i-1,j-1]，f[i,j-k]}篇裁，又要在所有決策中取最小值沛慢，所以動(dòng)態(tài)轉(zhuǎn)移方程是：
$f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}$
是否滿足最優(yōu)子結(jié)構(gòu)
得到了狀態(tài)轉(zhuǎn)移方程后，還需要判斷我們的思路是不是正確达布。能用動(dòng)態(tài)規(guī)劃解決的問(wèn)題必須要滿足一個(gè)特性团甲，叫做最優(yōu)子結(jié)構(gòu)特性。
一個(gè)最優(yōu)決策序列的任何子序列本身一定是相對(duì)于子序列的初始和結(jié)束狀態(tài)的最優(yōu)決策序列黍聂。
這句話是什么意思呢躺苦？舉個(gè)例子：f[4,5]表示4個(gè)雞蛋、5層樓時(shí)的最優(yōu)解产还，那它的子問(wèn)題f[3,4]匹厘，得到的解在3個(gè)雞蛋、4層樓時(shí)也是最優(yōu)解脐区，它所有的子問(wèn)題都滿足這個(gè)特性愈诚。那這就滿足了最優(yōu)子結(jié)構(gòu)特性。
一個(gè)反例
求 路徑長(zhǎng)度模10 結(jié)果最小的路徑
還是像上面那道題一樣牛隅，分成四個(gè)階段炕柔。
按照動(dòng)態(tài)規(guī)劃的解法，階段一CT倔叼，上面的路2 % 10 = 2汗唱，下面的路5 % 10 = 5，選擇上面那條丈攒，階段二BC也選擇上面那條哩罪，以此類推授霸，最后得出的結(jié)果路徑是藍(lán)色的這條。
但實(shí)際上际插，真正最優(yōu)的是紅色的這條路徑20 % 10 = 0碘耳。這就是因?yàn)?b>不符合最優(yōu)子結(jié)構(gòu)，對(duì)于紅色路徑的子結(jié)構(gòu)CT階段框弛，最優(yōu)解并不是下面這條邊辛辨。
時(shí)間復(fù)雜度
遞歸樹
假設(shè)m=3，n=4瑟枫，我們來(lái)看一下f[3,4]的遞歸樹斗搞。
圖中顏色相同的就是一樣的狀態(tài)，可以看出慷妙，重復(fù)的遞歸計(jì)算很多僻焚，因此我們開設(shè)一個(gè)數(shù)組result[i,j]用于存放f[i,j]的計(jì)算結(jié)構(gòu)，避免重復(fù)計(jì)算膝擂，用空間換時(shí)間虑啤。
代碼
class Solution {
private int[][] result;
public int superEggDrop(int K, int N) {
result = new int[K + 1][N + 1];
for (int i = 1; i < K + 1; i++) {
for (int j = 1; j < N + 1; j++) {
result[i][j] = -1;
}
}
return dp(K, N);
}
/**
* @param i 剩余雞蛋個(gè)數(shù)
* @param j 樓層高度
* @return
*/
private int dp(int i, int j) {
if (result[i][j] != -1) {
return result[i][j];
}
if (i == 1) {
return j;
}
if (j <= 1) {
return j;
}
int min = Integer.MAX_VALUE;
for (int k = 1; k <= j; k++) {
int left = dp(i - 1, k - 1);
result[i - 1][k - 1] = left;
int right = dp(i, j - k);
result[i][j - k] = right;
int res = Math.max(left, right) + 1;
if (res < min) {
min = res;
}
}
return min;
}
private static int log(int x) {
double r = (Math.log(x) / Math.log(2));
if ((r == Math.floor(r)) && !Double.isInfinite(r)) {
return (int) r;
} else {
return (int) r + 1;
}
}
}
時(shí)間復(fù)雜度
動(dòng)態(tài)規(guī)劃求時(shí)間復(fù)雜度的方法是：
時(shí)間復(fù)雜度 = 狀態(tài)總數(shù) * 狀態(tài)轉(zhuǎn)移方程的時(shí)間復(fù)雜度
在這道題中，狀態(tài)總個(gè)數(shù)很明顯是m*n架馋，而每個(gè)狀態(tài)f[i,j]的時(shí)間復(fù)雜度為$O(j)$狞山，$1 \leq j \leq n$，總時(shí)間復(fù)雜度為$O(mn^2)$叉寂。
優(yōu)化
$O(mn^2)$的時(shí)間復(fù)雜度還是太高了萍启。能不能想辦法優(yōu)化一下？
優(yōu)化1
決策樹
首先我們知道屏鳍，在一個(gè)1～n的數(shù)組中伊约，查找目標(biāo)數(shù)字，最少需要比較$log_2n$次孕蝉，也就是二分查找屡律。這個(gè)理論可以通過(guò)決策樹來(lái)證明：
我們使用二叉樹來(lái)表示所有的決策，內(nèi)部節(jié)點(diǎn)表示一次扔雞蛋的決策降淮，左子樹表示碎了超埋，右子樹表示沒(méi)碎，葉子節(jié)點(diǎn)代表E的所有結(jié)果佳鳖。每一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑對(duì)應(yīng)算法求出E之前的所有決策霍殴。
內(nèi)部節(jié)點(diǎn)(i,j)，i表示雞蛋個(gè)數(shù)系吩，j表示在j層樓扔下来庭。
當(dāng)樓層高度n=5時(shí)，E總共有6種情況（n=0代表沒(méi)找到）穿挨，所以葉子節(jié)點(diǎn)的個(gè)數(shù)是n+1個(gè)月弛。
而我們關(guān)心的是樹的高度肴盏，即決策的次數(shù)。根據(jù)二叉樹理論：當(dāng)樹有n個(gè)葉子節(jié)點(diǎn)帽衙，數(shù)的高度至少為$log_2n$菜皂，即比較次數(shù)在最壞情況下至少需要$log_2n$次，也就是當(dāng)這顆樹盡量平衡的時(shí)候厉萝。
換句話說(shuō)恍飘，在給定樓層n的情況下，決策次數(shù)的下限是$log_2(n+1)$谴垫，這個(gè)下限可以通過(guò)二分查找達(dá)到章母，只要雞蛋的數(shù)量足夠（就是我們剛才討論的不限雞蛋的情況）。
因此翩剪，一旦狀態(tài)f[i,j]的雞蛋個(gè)數(shù)$i>log_2(j+1)$胳施，就不用計(jì)算了，直接輸出二分查找的比較次數(shù)$log_2(j+1)$即可肢专。
這樣我們的狀態(tài)總數(shù)就降為$n*log_2(k+1)$，時(shí)間復(fù)雜度降為$O(n^2 log_2n)$焦辅。
代碼
/**
* @param i 剩余雞蛋個(gè)數(shù)
* @param j 樓層高度
* @return
*/
private int dp(int i, int j) {
if (result[i][j] != -1) {
return result[i][j];
}
if (i == 1) {
return j;
}
if (j <= 1) {
return j;
}
//此處剪枝優(yōu)化
int lowest = log(j + 1);
if (i > lowest) {
return lowest;
}
int min = Integer.MAX_VALUE;
for (int k = 1; k <= j; k++) {
int left = dp(i - 1, k - 1);
result[i - 1][k - 1] = left;
int right = dp(i, j - k);
result[i][j - k] = right;
int res = Math.max(left, right) + 1;
if (res < min) {
min = res;
}
}
return min;
}
優(yōu)化2
優(yōu)化還未結(jié)束博杖，我們嘗試從動(dòng)態(tài)轉(zhuǎn)移方程的函數(shù)性質(zhì)入手，觀察函數(shù)f(i,j)筷登，如下圖：
我們可以發(fā)現(xiàn)一個(gè)規(guī)律剃根，f(i,j)是根據(jù)j遞增的單調(diào)函數(shù)，即f(i,j)>=f(i,j-1)前方，這個(gè)性質(zhì)是可以用數(shù)學(xué)歸納法證明的狈醉，在這里不做證明，有興趣的查看文末參考文獻(xiàn)惠险。
再來(lái)看動(dòng)態(tài)轉(zhuǎn)移方程：
$f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}$
由于$f(i,j)$具有單調(diào)性苗傅，因此$f(i-1,k-1)$是根據(jù)k遞增的函數(shù)，$f(i,j-k)$是根據(jù)k遞減的函數(shù)班巩。
分別畫出這兩個(gè)函數(shù)的圖像：
圖像1：$f(i-1,k-1)$
圖像2：$f(i,j-k)$
圖像3：$max{f(i-1,k-1),f(i,j-k)}+1$渣慕，當(dāng)k=kbest時(shí)，f達(dá)到最小值抱慌，我們的目標(biāo)就是找到kbest的值逊桦。
對(duì)于這個(gè)函數(shù)，可以使用二分查找來(lái)找到kbest：
如果f(i-1,k-1)<f(i,j-k)抑进，則k<kbest强经，即k在圖中kbest的左邊；
如果f(i-1,k-1)>f(i,j-k)寺渗，則k>kbest匿情，即k在圖中kbest的右邊兰迫。
代碼
class EggDrop {
private int[][] result;
public int superEggDrop(int K, int N) {
result = new int[K + 1][N + 1];
for (int i = 1; i < K + 1; i++) {
for (int j = 1; j < N + 1; j++) {
result[i][j] = -1;
}
}
return dp(K, N);
}
/**
* @param i 剩余雞蛋個(gè)數(shù)
* @param j 樓層高度
* @return
*/
private int dp(int i, int j) {
if (result[i][j] != -1) {
return result[i][j];
}
if (i == 1) {
return j;
}
if (j <= 1) {
return j;
}
int lowest = log(j + 1);
if (i >= lowest) {
result[i][j] = lowest;
return lowest;
}
int left = 1, right = j;
while (left <= right) {
int k = (left + right) / 2;
int broken = dp(i - 1, k - 1);
result[i - 1][k - 1] = broken;
int notBroken = dp(i, j - k);
result[i][j - k] = notBroken;
if (broken < notBroken) {
left = k + 1;
} else if (broken > notBroken) {
right = k - 1;
} else {
return notBroken + 1;
}
}
//沒(méi)找到，最小值就在left或者right中
return Math.min(Math.max(dp(i - 1, left - 1), dp(i, j - left)),
Math.max(dp(i - 1, right - 1), dp(i, j - right))) + 1;
}
private static int log(int x) {
double r = (Math.log(x) / Math.log(2));
if ((r == Math.floor(r)) && !Double.isInfinite(r)) {
return (int) r;
} else {
return (int) r + 1;
}
}
}
時(shí)間復(fù)雜度
現(xiàn)在狀態(tài)轉(zhuǎn)移方程的時(shí)間復(fù)雜度降為了$O(log_2N)$码秉，算法的時(shí)間復(fù)雜度降為$O(Nlog_2^2 N)$逮矛。
優(yōu)化3
現(xiàn)在無(wú)論是狀態(tài)總數(shù)還是狀態(tài)轉(zhuǎn)移方程都很難優(yōu)化了，但還有一種算法有更低的時(shí)間復(fù)雜度转砖。
我們定義一個(gè)新的狀態(tài)g(i,j)须鼎，它表示用j個(gè)蛋嘗試i次在最壞情況下能確定E的最高樓層數(shù)。
動(dòng)態(tài)轉(zhuǎn)移方程
假設(shè)在k層扔下一只雞蛋：
如果碎了府蔗，則在后面的(i-1)次里晋控，我們要用(j-1)個(gè)蛋在下面的樓層中確定E。為了使 g(i,j)達(dá)到最大姓赤，我們當(dāng)然希望下面的樓層數(shù)達(dá)到最多赡译，這是一個(gè)子問(wèn)題，答案為 g(i-1,j-1)不铆。
如果沒(méi)碎蝌焚，則在后面(i-1)次里，我們要用j個(gè)蛋在上面的樓層中確定E誓斥，這同樣需要樓層數(shù)達(dá)到最多只洒，便為g(i-1,j) 。
因此動(dòng)態(tài)轉(zhuǎn)移方程為：
g(i,j)=g(i-1,j-1)+g(i-1,j)+1
邊界值
當(dāng)i=1時(shí)劳坑，表示只嘗試一次毕谴，那最多只能確定一層樓，即g(1,j)=1 (j>=1)
當(dāng)j=1是距芬，表示只有一個(gè)蛋涝开，那只能第一層一層層往上扔，最壞情況下一直扔到頂層框仔，即g(i,1)=i (i>=1)舀武。
然后我們的目標(biāo)就是找到一個(gè)嘗試次數(shù)x，使x滿足g(x-1,m)<n且g(x,m)>=n离斩。
代碼
public class EggDrop {
private int dp(int iTime, int j) {
if (iTime == 1) {
return 1;
}
if (j == 1) {
return iTime;
}
return dp(iTime - 1, j - 1) + dp(iTime - 1, j) + 1;
}
public int superEggDrop(int i, int j) {
int ans = 1;
while (dp(ans, i) < j) {
ans++;
}
return ans;
}
}
這個(gè)算法的時(shí)間復(fù)雜度是$O(\sqrt{N})$奕剃，證明比較復(fù)雜，這里就不展開了捐腿，可以參考文末文獻(xiàn)纵朋。
小結(jié)
最后我們總結(jié)一下動(dòng)態(tài)規(guī)劃算法的解題方法：
四步走：?jiǎn)栴}建模、定義子問(wèn)題茄袖、動(dòng)態(tài)轉(zhuǎn)移方程操软、最優(yōu)子結(jié)構(gòu)。
時(shí)間復(fù)雜度 = 狀態(tài)總數(shù) * 狀態(tài)轉(zhuǎn)移方程的時(shí)間復(fù)雜度宪祥。
考慮是否需要設(shè)置標(biāo)記聂薪，例如有的題目還要求打印出最小路徑家乘。
寫代碼，遞歸和循環(huán)選擇你熟悉的來(lái)寫藏澳。
如果時(shí)間復(fù)雜度不能接受仁锯，考慮能不能優(yōu)化算法。
優(yōu)化思路
是否能夠剪枝優(yōu)化（優(yōu)化1）
從函數(shù)本身的數(shù)學(xué)性質(zhì)入手（優(yōu)化2）
轉(zhuǎn)換思路翔悠，嘗試一下別的狀態(tài)轉(zhuǎn)移方程（優(yōu)化3）
……
動(dòng)態(tài)規(guī)劃在算法中屬于較難的題型业崖，難點(diǎn)就在定義子問(wèn)題和寫出動(dòng)態(tài)轉(zhuǎn)移方程。所以需要勤加練習(xí)蓄愁，訓(xùn)練自己的思維双炕。
這里給出幾道動(dòng)態(tài)規(guī)劃的經(jīng)典題目，這幾道題都需要吃透撮抓，可以用本文中提到的四步走的方式來(lái)思考和解題妇斤。
Maximum Length of Repeated Subarray
Coin Change
Partition Equal Subset Sum
關(guān)注我了解更多程序員資訊技術(shù)，領(lǐng)取豐富架構(gòu)資料
