肺炎疫情期間，在B站上看了李永樂老師關於雙蛋問題的視頻，剛好我最近寫了一篇關於動態規劃的文章，這裡我們試著使用動態規劃的思想簡單分析下這個問題。
一、問題描述
有一座100層的樓，有一個雞蛋，在低樓層的時候將雞蛋扔下不會碎，但是高樓層扔下會碎。存在一個臨界樓層從該樓層之上拋下來，雞蛋一定會碎。現在有N個雞蛋可以做檢查（雞蛋沒碎可以重複使用，但是碎了就不能使用了），問最少幾次（M）能夠找到這個臨界樓層。
二、嘗試
1）假設N=1，為了確保雞蛋不會碎，只能從第一層開始往上扔，直到雞蛋碎了為止，最差M=100
2）假設雞蛋有無限多，可以使用二分法來解決這個問題，即在第50層往下扔，如果雞蛋碎了就在25層繼續扔，如果沒碎的話，在75層往下扔。依次類推，直到找到為止。2^M>=100，m約等於6.64
如果N=2的情況下，最好需要多少次才能試出M？
1）假設第一個雞蛋每隔十層扔一次，10、20、30。。。100，等雞蛋碎著之後從再從區間內開始嘗試，如果在第100層碎了的話就是91-99，這樣就可以試出臨界樓層了。
臨界樓層出現在100層碎掉的話最壞的情況就是先扔10次（100／10=10）然後在91、92、93.。。99層向下扔，M=10+9=19。臨界樓層出現在10層碎掉的話最壞的情況就是先扔1次（10/10=1），然後在1、2、3。。。9層向下扔要10次，M=1+9=10
當然我們可以通過擴大、減小第一次扔雞蛋相隔樓層的數可以減少第二次扔雞蛋的次數，但是這種情況計算出的結果也並不一定就是最優解，所以我們可以引入動態規劃的思量來解決這個問題。
三、動態規劃
假設有t層樓和n個雞蛋，我們要如何計算出這個問題呢？
設M(t,n)為在從t層樓，n個蛋的情況下需要拋投的最少次數，假設在k層樓進行拋投，會產生兩種情況：
如果雞蛋碎了，那麼我們需要繼續計算的就是M(k, n-1)（n-1是因為雞蛋碎了）
如果雞蛋沒碎，那麼我們需要繼續計算的就是M(t-k, n)
因為我們需要找到最壞的情況，所以我們需要去兩者中的最大值
因此我們可以得出，在k層扔下第一顆雞蛋Mk(t,n) = max(M(k-1, n-1), M(t-k, n)) + 1
k值可能為1-t次，因此想要找拋投的最少次數為M(t,n)= min(M1(t,n), M2(t,n), M3(t,n) ...... Mk(t,n))
在t=1或者n=1的時候，我們能夠清楚的計算出M(t,n)，這就是該問題的邊界。
有了邊界和狀態轉移公式，我們就可以通過代碼實現這個問題
public static int getMin(int t, int n) {
int[][] dp = new int[t + 1][n + 1];
// 邊界處理,只有一個雞蛋，i層就要扔i次
for (int i = 1; i < t + 1; i++) {
dp[i][1] = i;
}
// 邊界處理,只有一層，不論雞蛋有幾個只要扔一次就可以
for (int j = 1; j < n + 1; j++) {
dp[1][j] = 1;
}
for (int i = 2; i < t + 1; i++) {
for (int j = 2; j < n + 1; j++) {
int min = Integer.MAX_VALUE;
for (int k = 1; k < i; k++) {
min = Math.min(min, Math.max(dp[i - k][j], dp[k - 1][j - 1]) + 1);
}
dp[i][j] = min;
}
}
return dp[t][n];
}
閱讀更多 加班狗的微博 的文章
