?leetcode頂級難題，谷歌面試天天問，來看看吧，帶你來一步一步達到最優解。

谷歌不知道問了多少遍，藍橋杯也出現過，leetcode上是頂級難題，到底是什么題能如此頻繁地出現？我們一探究竟吧。

原題描述：

????????x星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機。
各大廠商也就紛紛推出各種耐摔型手機。x星球的質監局規定了手機必須經過耐摔測試，并且評定出一個耐摔指數來，之后才允許上市流通。
????????x星球有很多高聳入云的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當于我們的2樓。
????????如果手機從第7層扔下去沒摔壞，但第8層摔壞了，則手機耐摔指數=7。

特別地，如果手機從第1層扔下去就壞了，則耐摔指數=0。如果到了塔的最高層第n層扔沒摔壞，則耐摔指數=n

????????為了減少測試次數，從每個廠家抽樣3部手機參加測試。
????????某次測試的塔高為1000層，如果我們總是采用最佳策略，在最壞的運氣下最多需要測試多少次才能確定手機的耐摔指數呢？
????????請填寫這個最多測試次數。

????????注意：需要填寫的是一個整數，不要填寫任何多余內容

答案19

?

文章目的

?

讀完題后，我們追求的不是要寫出得數，而是用代碼實現方法，并思考是否可以優化。

其實本題的方法是非常多種多樣的。非常適合鍛煉思維。

我們把問題擴展到n個手機來思考。

手機k個，樓n層，最終結果M次。

時空復雜度目錄

暴力：? ? ? ? ? ? ? ? ? ? ? ? O(N!)

DP:? ? ? ? ? ? ? ? ? ? ? ? ? ? O(N*N*K)? O(N*K)

壓空間：? ? ? ? ? ? ? ? ? ? O(N*N*K)? O(N)

四邊形不等式優化? ? ?O(N*N)? ? ? ?

換思路：? ? ? ? ? ? ? ? ? ? O(K*M)

最優：? ? ? ? ? ? ? ? ? ? ? ? ?O(K*M)? ? O(N)

文末有測試，大家可以去直觀感受一下各方法運行的效率

二分

?

容易想到二分思路：不斷二分范圍，取中點，測驗是否會摔壞，然后縮小一半范圍，繼續嘗試，很顯然，答案為logN（2為底）

但是，二分得出的答案是不對的。注意:我們要保證在都手機摔完之前，能確定耐摔指數到底是多少。

舉例：

我們在500樓摔壞了，在250樓摔，又壞了。接下來，我們只能從1樓開始一層一層試

因為如果我們在125層摔壞了，就沒有手機可以用，也就是永遠都測不出來，而這是不被允許的。其實我們連測第2層都不敢測，因為在第2層摔壞了，我們就無法知道手機在第一層能否被摔壞。所以只有一部手機時，我們只敢從第一層開始摔。

?

嘗試較優的策略

?

既然二分是不對的，我們繼續分析：摔手機的最優策略到底是如何的。

只有一部手機時，我們只敢從第一層開始摔。

有兩部手機的時候，我們就敢隔層摔了，因為一部手機壞了，我們還有另一部來繼續試。

這時就有點意思了，我們分析情況：

情況1）假設我們第一部手機在i層摔壞了，然后最壞情況還要試多少次？這時我們還剩一部手機，所以只敢一層一層試，最壞情況要試到i-1層，共試了i次。

情況2）假設我們第一部手機在i層試了，但是沒摔壞，然后最壞情況還要試多少次？（這時發現算情況2時依舊是相似的問題，確定了可以用遞歸來解。）

?

最優解（最小值）是決策后兩種情況的最差情況（最大值），我們的本能感覺應該就是讓最差情況好一點，讓最好情況差一點，這樣比較接近正確答案。比如兩部手機，一百層，我們可以在50層摔，沒壞，這一次就很賺，我們沒摔壞手機還把范圍縮小了50層。如果壞了，就比較坑了，我們要從1試到50。雖然可能縮小一半，但是最壞情況次數太多，所以肯定要從某個低于五十的層開始嘗試。

（以上幾行是為了讓讀者理解決策，下面正文分析）

?

歸納表達式

?

假設我們的樓一共n層，我們的i可以取1-n任意值，有很多種可能的決策，我們的最小值設為f（n，k），n代表樓高（范圍為1-100或101-200其實都一樣），k代表手機數.

我們假設的決策是在第i樓扔

對于情況一，手機少了一部，并且我們確定了范圍，一定在第i樓以下，所以手機-1，層數為i-1，這時f（n，k）=f(i-1,k-1).+1

對于情況二，手機沒少，并且我們確定了范圍，一定在第i樓之上，所以手機數不變，而層數-i層，這時f（n，k）=f(n-i,k).+1

歸納出

f（n，k）=min（? max（f(i-1,k-1) ，f(n-i,k)?）?i取1-n任意數 ? ?）+1

簡單總結：怎么確定第一個手機在哪扔？每層都試試，哪層的最壞情況（max）最好（min），就去哪層扔。

?

寫出暴力遞歸

按照分析出來的表達式，我們可以寫出暴力遞歸：

	public static int solution1(int nLevel, int kChess) {if (nLevel == 0) {return 0;}//范圍縮小至0if (kChess == 1) {return nLevel;}//每層依次試int min = Integer.MAX_VALUE;//取不影響結果的數for (int i = 1; i != nLevel + 1; i++) {//嘗試所有決策，取最優min = Math.min(min,Math.max(Process1(i - 1, kChess - 1),Process1(nLevel - i, kChess)));}return min + 1;//別忘了加上本次}

?

改為動態規劃

?

具體思路如下

https://blog.csdn.net/hebtu666/article/details/79912328

	public static int solution2(int nLevel, int kChess) {if (kChess == 1) {return nLevel;}int[][] dp = new int[nLevel + 1][kChess + 1];for (int i = 1; i != dp.length; i++) {dp[i][1] = i;}for (int i = 1; i != dp.length; i++) {for (int j = 2; j != dp[0].length; j++) {int min = Integer.MAX_VALUE;for (int k = 1; k != i + 1; k++) {min = Math.min(min,Math.max(dp[k - 1][j - 1], dp[i - k][j]));}dp[i][j] = min + 1;}}return dp[nLevel][kChess];}

?

壓縮空間

?

我們發現，對于狀態轉移方程，只和上一盤排的dp表和左邊的dp表有關，所以我們不需要把值全部記錄，用兩個長度為n的數組不斷更新即可（具體對dp壓縮空間的思路，也是很重要的，我在其它文章中有提過，在這里就不寫了）

	public static int solution3(int nLevel, int kChess) {if (kChess == 1) {return nLevel;}int[] preArr = new int[nLevel + 1];int[] curArr = new int[nLevel + 1];for (int i = 1; i != curArr.length; i++) {curArr[i] = i;}//初始化for (int i = 1; i != kChess; i++) {//先交換int[] tmp = preArr;preArr = curArr;curArr = tmp;//然后打新的一行for (int j = 1; j != curArr.length; j++) {int min = Integer.MAX_VALUE;for (int k = 1; k != j + 1; k++) {min = Math.min(min, Math.max(preArr[k - 1], curArr[j - k]));}curArr[j] = min + 1;}}return curArr[curArr.length - 1];}

?

四邊形不等式優化

?

四邊形不等式是一種比較常見的優化動態規劃的方法

定義：如果對于任意的a1≤a2<b1≤b2，有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1]，那么m[i,j]滿足四邊形不等式。

對s[i,j-1]≤s[i,j]≤s[i+1,j]的證明：

設mk[i,j]=m[i,k]+m[k,j]，s[i,j]=d

對于任意k<d，有mk[i,j]≥md[i,j]（這里以m[i,j]=min{m[i,k]+m[k,j]}為例,max的類似），接下來只要證明mk[i+1,j]≥md[i+1,j]，那么只有當s[i+1,j]≥s[i,j]時才有可能有mk[i+1,j]≥md[i+1,j]

(mk[i+1,j]-md[i+1,j])-(mk[i,j]-md[i,j])

=(mk[i+1,j]+md[i,j])-(md[i+1,j]+mk[i,j])

=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j])-(m[i+1,d]+m[d,j]+m[i,k]+m[k,j])

=(m[i+1,k]+m[i,d])-(m[i+1,d]+m[i,k])

∵m滿足四邊形不等式，∴對于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]

∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0

∴s[i,j]≤s[i+1,j]，同理可證s[i,j-1]≤s[i,j]

證畢

?

通俗來說，

優化策略1）我們在求k+1手機n層樓時，最后發現，第一個手機在m層扔導致了最優解的產生。那我們在求k個手機n層樓時，第一個手機的策略就不用嘗試m層以上的樓了。

優化策略2）我們在求k個手機n層樓時，最后發現，第一個手機在m層扔導致了最優解的產生。那我們在求k個手機n+1層樓時，就不用嘗試m層以下的樓了。

	public static int solution4(int nLevel, int kChess) {if (kChess == 1) {return nLevel;}int[][] dp = new int[nLevel + 1][kChess + 1];for (int i = 1; i != dp.length; i++) {dp[i][1] = i;}int[] cands = new int[kChess + 1];for (int i = 1; i != dp[0].length; i++) {dp[1][i] = 1;cands[i] = 1;}for (int i = 2; i < nLevel + 1; i++) {for (int j = kChess; j > 1; j--) {int min = Integer.MAX_VALUE;int minEnum = cands[j];int maxEnum = j == kChess ? i / 2 + 1 : cands[j + 1];//優化策略for (int k = minEnum; k < maxEnum + 1; k++) {int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);if (cur <= min) {min = cur;cands[j] = k;//最優解記錄層數}}dp[i][j] = min + 1;}}return dp[nLevel][kChess];}

注：對于四邊形不等式的題目，比賽時不需要嚴格證明

通常的做法是打表出來之后找規律，然后大膽猜測，顯然可得。（手動滑稽）

?

換一種思路

?

有時，最優解并不是優化來的。

當你對著某個題冥思苦想了好久，無論如何也不知道怎么把時間優化到合理范圍，可能這個題的最優解就不是這種思路，這時，試著換一種思路思考，可能會有奇效。

（比如訓練時一道貪心我死活往dp想，肝了兩個小時以后，不主攻這個方向的隊友三分鐘就有貪心思路了，淚目，不要把簡單問題復雜化）

?

我們換一種思路想問題：

原問題：n層樓，k個手機，最多測試次數

反過來看問題：k個手機，扔m次，最多能確定多少層樓？

我們定義dp[i][j]：i個手機扔j次能確定的樓數。

分析情況：依舊是看第一部手機在哪層扔的決策，同樣，我們的決策首先要保證能確定從1層某一段，而不能出現次數用完了還沒確定好的情況。以這個為前提，保證了每次扔的樓層都是最優的，就能求出結果。

依舊是取最壞情況：min（情況1，情況2）

情況1）第一個手機碎了，我們就需要用剩下的i-1個手機和j-1次測試次數往下去測，dp[i-1][j-1]。那我們能確定的層數是無限的，因為本層以上的無限層樓都不會被摔壞。dp[i-1][j-1]+無窮=無窮

情況2）第一個手機沒碎，那我們就看i個手機扔j-1次能確定的樓數（向上試）+當前樓高h

歸納表達式，要取最差情況，所以就是只有情況2：dp[i][j]=dp[i-1][j-1]+h

那這個h到底是什么呢？取決于我敢從哪層扔。因為次數減了一次，我們還是要考慮i個球和j-1次的最壞情況能確定多少層，我才敢在層數+1的地方扔。（這是重點）

也就是dp[i][j-1]的向上一層：h=dp[i][j-1]+1

?

總：min（情況1，情況2）=min（無窮，dp[i-1][j-1]+dp[i][j-1]+1）=dp[i-1][j-1]+dp[i][j-1]+1

這是解決k個手機，扔m次，最多能確定多少層樓？

原問題是n層樓，k個手機，最多測試次數。

所以我們在求的過程中，何時能確定的層數大于n，輸出扔的次數即可

?

最優解

我們知道完全用二分扔需要logN+1次，這也絕對是手機足夠情況下的最優解，我們做的這么多努力都是因為手機不夠摔啊。。。。所以當我們的手機足夠用二分來摔時，直接求出logN+1即可。

?

當然，我們求dp需要左邊的值和左上的值：

依舊可以壓縮空間，從左往右更新，previous記錄左上的值。

求自己時也要注意記錄，否則更新過后，后面的要用沒更新過的值（左上方）就找不到了。

記錄之后，求出當前數值，把記錄的temp值給了previous即可。

	public static int solution5(int nLevel, int kChess) {int bsTimes = log2N(nLevel) + 1;if (kChess >= bsTimes) {return bsTimes;}int[] dp = new int[kChess];int res = 0;while (true) {res++;//壓縮空間記得記錄次數int previous = 0;for (int i = 0; i < dp.length; i++) {int tmp = dp[i];dp[i] = dp[i] + previous + 1;previous = tmp;if (dp[i] >= nLevel) {return res;}}}}public static int log2N(int n) {int res = -1;while (n != 0) {res++;n >>>= 1;}return res;}

?

?

?

?

本題只是填空題，第一種方法就完全能算出來，就是為了追求最優解，追求思維的鍛煉。寫下了本文。

?

?

測試：

暴力：? ? ? ? ? ? ? ? ? ? ? ? O(N!)

DP:? ? ? ? ? ? ? ? ? ? ? ? ? ? O(N*N*K)? O(N*K)

壓空間：? ? ? ? ? ? ? ? ? ? O(N*N*K)? O(N)

四邊形不等式優化? ? ?O(N*N)? ? ? ?

最優：? ? ? ? ? ? ? ? ? ? ? ? ?O(K*M)? ? O(N)

		long start = System.currentTimeMillis();solution1(30, 2);long end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + " ms");start = System.currentTimeMillis();solution2(30, 2);end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + " ms");start = System.currentTimeMillis();solution3(30, 2);end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + " ms");start = System.currentTimeMillis();solution4(30, 2);end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + " ms");start = System.currentTimeMillis();solution5(30, 2);end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + " ms");
/*
結果：
cost time: 7043 ms
cost time: 0 ms
cost time: 0 ms
cost time: 0 ms
cost time: 0 ms
*/

暴力時間實在是太久了，只測一個30，2

?

后四種方法測的大一些（差點把電腦測炸了，cpu100內存100）：

solution(100000, 10):

solution2 cost time: 202525 ms
solution3 cost time: 38131 ms
solution4 cost time: 11295 ms
solution5 cost time: 0 ms

?

感受最優解的強大：

solution5(1000 000 000,100):0 ms

solution5(1000 000 000,10):0 ms

最優解永遠都是0 ms，我也是服了。。

?

對比方法，在時間復雜度相同的條件下，空間復雜度一樣會影響時間，因為空間太大的話，申請空間是相當浪費時間的。并且空間太大電腦會炸，所以不要認為空間不重要。