假設你面前有一棟n層的大樓和m個雞蛋，假設將雞蛋從f層或更高的地方放扔下去，雞蛋才會碎，否則就不會。你需要設計一種策略來確定f的值，求最壞情況下扔雞蛋次數(shù)的最小值。

乍一看這道題很抽象，可能有的人一看到這個題目從來沒做過，就懵逼了。其實不用慌張，再花里胡哨的題目，最后都可以抽象成我們熟悉的數(shù)據結構和算法去解決。

不限雞蛋

首先，我們從一個簡單的版本開始理解，假如不限制雞蛋個數(shù)，即把題目改成n層大樓和無限個雞蛋。那么這題要怎么解呢？

第一步就是要充分理解題意，排除題目中的干擾，建立模型：

在一棟n層的大樓中尋找目標樓層f --> 其實就是在一個1～n的數(shù)組中查找一個目標數(shù)字。

雞蛋碎了就代表樓層過高，否則就代表樓層過低 --> 每次嘗試都能知道當前數(shù)字是大了還是小了。

很顯然，這就是一個二分查找能解決的問題。

扔雞蛋的次數(shù)就是二分查找的比較次數(shù)，即$log_2(n+1)$。

限制雞蛋個數(shù)

那我們現(xiàn)在再來看限制雞蛋個數(shù)情況下，肯定沒法用二分查找，但是由于求解的是一個最優(yōu)值，我們自然而然地想到了動態(tài)規(guī)劃。

四步走

動態(tài)規(guī)劃的題目，這邊提供一個思路，就是四步走：

問題建模，優(yōu)化的目標函數(shù)是什么？約束條件是什么？

劃分子問題（狀態(tài)）

列出狀態(tài)轉移方程及初值

是否滿足最優(yōu)子結構性質

建模

這一步非常非常重要，它建立在良好地理解題意的基礎上。其實很多動態(tài)規(guī)劃的題目都有這樣的特點：

目標是求一個最優(yōu)值

每一步決策有代價，總代價有一個約束值。

而這道題：

目標函數(shù)f(n)：代表在1～n的樓層中找到f層的嘗試次數(shù)，我們的目標就是求出f(n)的最優(yōu)值。

每一步決策的代價：雞蛋可能會碎；總代價的約束值：雞蛋總個數(shù)。

劃分子問題

我們知道動態(tài)規(guī)劃就是多階段決策的過程，最后求解組合最優(yōu)值。

我們先舉一個簡單例子，來理解劃分子問題的思路，看下面這張圖:

問題：求起點集 S1～S5到終點集 T1～T5的最短路徑。

分析這道題：定義子問題dis[i]代表節(jié)點i到終點的最短距離，沒有約束條件。

然后問題劃分為4個階段：

階段1求出離終點最近的C1~C4節(jié)點到終點的最短路徑dis[C1]~dis[C4]。

階段2求出離終點最近的B2~B5節(jié)點到終點的最短路徑dis[B1]~dis[B5]，需要建立在階段1的結果上計算。例如B2節(jié)點到終點有兩條路，B2～C1，B2～C2，dis[C1]=2，B2到C1的長度=3；而dis[C2]=3，B2到C2的長度=6，因此dis[B2]=3+dis[B1]=5。

階段3和階段4也是以此類推，最終就求出得到dis[S1]~dis[S5]，得出最小路徑為圖中紅色的兩條。

在這道題中，dis[i]就是劃分出來的子問題，每一步決策都是一個子問題，而且每一個子問題都依賴于以前子問題的計算結果。

因此，在動態(tài)規(guī)劃中，定義一個合理的子問題非常重要。

而扔雞蛋這道題比上面這道題多了個約束條件，我們把子問題定義為：用i個雞蛋，在j層樓上扔，在最壞情況下確定目標樓層E的最少次數(shù)，記為狀態(tài)f[i,j]。

列出狀態(tài)轉移方程和初值

假如決策是在第k層扔下雞蛋，有兩種結果：

雞蛋碎了，此時e<k，我們只能用i-1個蛋在下面的j-1層繼續(xù)尋找e。并且要求最壞情況下的次數(shù)最少，這是一個子問題，答案為f[i-1,j-1]，總次數(shù)便是f[i-1,j-1]+1。

雞蛋沒碎，此時e>=k，我們繼續(xù)用這i個蛋在上面的j-k層尋找E。注意：在k～j層尋找和在1～(j-k)層尋找沒有區(qū)別，因為步驟都是一樣的，只不過這(j-k)層在上面罷了，所以就把它看成是對1～(j-k)層的操作。因此答案為f[i,j-k]，次數(shù)為f[i,j-k]+1。

初值：

當層數(shù)為0時，f[i,0]=0，當雞蛋個數(shù)為1時，只能從下往上一層層扔，f[1,j]=j。

因為是要最壞情況，所以這兩種情況要取大值：max{f[i-1,j-1]，f[i,j-k]}，又要在所有決策中取最小值，所以動態(tài)轉移方程是：

$f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}$

是否滿足最優(yōu)子結構

得到了狀態(tài)轉移方程后，還需要判斷我們的思路是不是正確。能用動態(tài)規(guī)劃解決的問題必須要滿足一個特性，叫做最優(yōu)子結構特性。

一個最優(yōu)決策序列的任何子序列本身一定是相對于子序列的初始和結束狀態(tài)的最優(yōu)決策序列。

這句話是什么意思呢？舉個例子：f[4,5]表示4個雞蛋、5層樓時的最優(yōu)解，那它的子問題f[3,4]，得到的解在3個雞蛋、4層樓時也是最優(yōu)解，它所有的子問題都滿足這個特性。那這就滿足了最優(yōu)子結構特性。

一個反例

求 路徑長度模10 結果最小的路徑

還是像上面那道題一樣，分成四個階段。

按照動態(tài)規(guī)劃的解法，階段一CT，上面的路2 % 10 = 2，下面的路5 % 10 = 5，選擇上面那條，階段二BC也選擇上面那條，以此類推，最后得出的結果路徑是藍色的這條。

但實際上，真正最優(yōu)的是紅色的這條路徑20 % 10 = 0。這就是因為不符合最優(yōu)子結構，對于紅色路徑的子結構CT階段，最優(yōu)解并不是下面這條邊。

時間復雜度

遞歸樹

假設m=3，n=4，我們來看一下f[3,4]的遞歸樹。

圖中顏色相同的就是一樣的狀態(tài)，可以看出，重復的遞歸計算很多，因此我們開設一個數(shù)組result[i,j]用于存放f[i,j]的計算結構，避免重復計算，用空間換時間。

代碼

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 剩余雞蛋個數(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;

}

}

}

時間復雜度

動態(tài)規(guī)劃求時間復雜度的方法是：

時間復雜度 = 狀態(tài)總數(shù) * 狀態(tài)轉移方程的時間復雜度

在這道題中，狀態(tài)總個數(shù)很明顯是m*n，而每個狀態(tài)f[i,j]的時間復雜度為$O(j)$，$1 \leq j \leq n$，總時間復雜度為$O(mn^2)$。

優(yōu)化

$O(mn^2)$的時間復雜度還是太高了。能不能想辦法優(yōu)化一下？

優(yōu)化1

決策樹

首先我們知道，在一個1～n的數(shù)組中，查找目標數(shù)字，最少需要比較$log_2n$次，也就是二分查找。這個理論可以通過決策樹來證明：

我們使用二叉樹來表示所有的決策，內部節(jié)點表示一次扔雞蛋的決策，左子樹表示碎了，右子樹表示沒碎，葉子節(jié)點代表E的所有結果。每一條從根節(jié)點到葉子節(jié)點的路徑對應算法求出E之前的所有決策。

內部節(jié)點(i,j)，i表示雞蛋個數(shù)，j表示在j層樓扔下。

當樓層高度n=5時，E總共有6種情況（n=0代表沒找到），所以葉子節(jié)點的個數(shù)是n+1個。

而我們關心的是樹的高度，即決策的次數(shù)。根據二叉樹理論：當樹有n個葉子節(jié)點，數(shù)的高度至少為$log_2n$，即比較次數(shù)在最壞情況下至少需要$log_2n$次，也就是當這顆樹盡量平衡的時候。

換句話說，在給定樓層n的情況下，決策次數(shù)的下限是$log_2(n+1)$，這個下限可以通過二分查找達到，只要雞蛋的數(shù)量足夠（就是我們剛才討論的不限雞蛋的情況）。

因此，一旦狀態(tài)f[i,j]的雞蛋個數(shù)$i>log_2(j+1)$，就不用計算了，直接輸出二分查找的比較次數(shù)$log_2(j+1)$即可。

這樣我們的狀態(tài)總數(shù)就降為$n*log_2(k+1)$，時間復雜度降為$O(n^2 log_2n)$。

代碼

/**

* @param i 剩余雞蛋個數(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)化還未結束，我們嘗試從動態(tài)轉移方程的函數(shù)性質入手，觀察函數(shù)f(i,j)，如下圖：

我們可以發(fā)現(xiàn)一個規(guī)律，f(i,j)是根據j遞增的單調函數(shù)，即f(i,j)>=f(i,j-1)，這個性質是可以用數(shù)學歸納法證明的，在這里不做證明，有興趣的查看文末參考文獻。

再來看動態(tài)轉移方程：

$f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}$

由于$f(i,j)$具有單調性，因此$f(i-1,k-1)$是根據k遞增的函數(shù)，$f(i,j-k)$是根據k遞減的函數(shù)。

分別畫出這兩個函數(shù)的圖像：

圖像1：$f(i-1,k-1)$

圖像2：$f(i,j-k)$

圖像3：$max{f(i-1,k-1),f(i,j-k)}+1$，當k=kbest時，f達到最小值，我們的目標就是找到kbest的值。

對于這個函數(shù)，可以使用二分查找來找到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 剩余雞蛋個數(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;

}

}

//沒找到，最小值就在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;

}

}

}

時間復雜度

現(xiàn)在狀態(tài)轉移方程的時間復雜度降為了$O(log_2N)$，算法的時間復雜度降為$O(Nlog_2^2 N)$。

優(yōu)化3

現(xiàn)在無論是狀態(tài)總數(shù)還是狀態(tài)轉移方程都很難優(yōu)化了，但還有一種算法有更低的時間復雜度。

我們定義一個新的狀態(tài)g(i,j)，它表示用j個蛋嘗試i次在最壞情況下能確定E的最高樓層數(shù)。

動態(tài)轉移方程

假設在k層扔下一只雞蛋：

如果碎了，則在后面的(i-1)次里，我們要用(j-1)個蛋在下面的樓層中確定E。為了使 g(i,j)達到最大，我們當然希望下面的樓層數(shù)達到最多，這是一個子問題，答案為 g(i-1,j-1)。

如果沒碎，則在后面(i-1)次里，我們要用j個蛋在上面的樓層中確定E，這同樣需要樓層數(shù)達到最多，便為g(i-1,j) 。

因此動態(tài)轉移方程為：

g(i,j)=g(i-1,j-1)+g(i-1,j)+1

邊界值

當i=1時，表示只嘗試一次，那最多只能確定一層樓，即g(1,j)=1 (j>=1)

當j=1是，表示只有一個蛋，那只能第一層一層層往上扔，最壞情況下一直扔到頂層，即g(i,1)=i (i>=1)。

然后我們的目標就是找到一個嘗試次數(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;

}

}

這個算法的時間復雜度是$O(\sqrt{N})$，證明比較復雜，這里就不展開了，可以參考文末文獻。

小結

最后我們總結一下動態(tài)規(guī)劃算法的解題方法：

四步走：問題建模、定義子問題、動態(tài)轉移方程、最優(yōu)子結構。

時間復雜度 = 狀態(tài)總數(shù) * 狀態(tài)轉移方程的時間復雜度。

考慮是否需要設置標記，例如有的題目還要求打印出最小路徑。

寫代碼，遞歸和循環(huán)選擇你熟悉的來寫。

如果時間復雜度不能接受，考慮能不能優(yōu)化算法。

優(yōu)化思路

是否能夠剪枝優(yōu)化（優(yōu)化1）

從函數(shù)本身的數(shù)學性質入手（優(yōu)化2）

轉換思路，嘗試一下別的狀態(tài)轉移方程（優(yōu)化3）

……

動態(tài)規(guī)劃在算法中屬于較難的題型，難點就在定義子問題和寫出動態(tài)轉移方程。所以需要勤加練習，訓練自己的思維。

這里給出幾道動態(tài)規(guī)劃的經典題目，這幾道題都需要吃透，可以用本文中提到的四步走的方式來思考和解題。

Maximum Length of Repeated Subarray

Coin Change

Partition Equal Subset Sum

關注我了解更多程序員資訊技術，領取豐富架構資料