# 0887. 雞蛋掉落 ## 題目地址()887. 雞蛋掉落 <https://leetcode-cn.com/problems/super-egg-drop/> ## 題目描述 ``` <pre class="calibre18">``` 你將獲得 K 個雞蛋，并可以使用一棟從 1 到 N 共有 N 層樓的建筑。 每個蛋的功能都是一樣的，如果一個蛋碎了，你就不能再把它掉下去。 你知道存在樓層 F ，滿足 0 <= F <= N 任何從高于 F 的樓層落下的雞蛋都會碎，從 F 樓層或比它低的樓層落下的雞蛋都不會破。 每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）并把它從任一樓層 X 扔下（滿足 1 <= X <= N）。 你的目標是確切地知道 F 的值是多少。 無論 F 的初始值如何，你確定 F 的值的最小移動次數是多少？ 示例 1： 輸入：K = 1, N = 2 輸出：2 解釋： 雞蛋從 1 樓掉落。如果它碎了，我們肯定知道 F = 0 。 否則，雞蛋從 2 樓掉落。如果它碎了，我們肯定知道 F = 1 。 如果它沒碎，那么我們肯定知道 F = 2 。 因此，在最壞的情況下我們需要移動 2 次以確定 F 是多少。 示例 2： 輸入：K = 2, N = 6 輸出：3 示例 3： 輸入：K = 3, N = 14 輸出：4 提示： 1 <= K <= 100 1 <= N <= 10000 ``` ``` ## 前置知識 - 動態規劃 ## 思路 > 本題已經重制，重制版更清晰 [《丟雞蛋問題》重制版來襲～](https://lucifer.ren/blog/2020/06/08/887.super-egg-drop/) 這是一道典型的動態規劃題目，但是又和一般的動態規劃不一樣。 拿題目給的例子為例，兩個雞蛋，六層樓，我們最少扔幾次？  一個符合直覺的做法是，建立 dp\[i\]\[j\], 代表 i 個雞蛋，j 層樓最少扔幾次，然后我們取 dp\[K\]\[n\]即可。 代碼大概這樣的： ``` <pre class="calibre18">``` <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(K + <span class="hljs-params">1</span>); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">Array</span>(N + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < K + <span class="hljs-params">1</span>; i++) { dp[i] = [<span class="hljs-params">0</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j < N + <span class="hljs-params">1</span>; j++) { <span class="hljs-title">// 只有一個雞蛋</span> <span class="hljs-keyword">if</span> (i === <span class="hljs-params">1</span>) { dp[i][j] = j; <span class="hljs-keyword">continue</span>; } <span class="hljs-title">// 只有一層樓</span> <span class="hljs-keyword">if</span> (j === <span class="hljs-params">1</span>) { dp[i][j] = <span class="hljs-params">1</span>; <span class="hljs-keyword">continue</span>; } <span class="hljs-title">// 每一層我們都模擬一遍</span> <span class="hljs-keyword">const</span> all = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> k = <span class="hljs-params">1</span>; k < j + <span class="hljs-params">1</span>; k++) { <span class="hljs-keyword">const</span> brokenCount = dp[i - <span class="hljs-params">1</span>][k - <span class="hljs-params">1</span>]; <span class="hljs-title">// 如果碎了</span> <span class="hljs-keyword">const</span> notBrokenCount = dp[i][j - k]; <span class="hljs-title">// 如果沒碎</span> all.push(<span class="hljs-params">Math</span>.max(brokenCount, notBrokenCount)); <span class="hljs-title">// 最壞的可能</span> } dp[i][j] = <span class="hljs-params">Math</span>.min(...all) + <span class="hljs-params">1</span>; <span class="hljs-title">// 最壞的集合中我們取最好的情況</span> } } <span class="hljs-keyword">return</span> dp[K][N]; ``` ``` 果不其然，當我提交的時候，超時了。 這個的時復雜度是很高的，可以看到，我們內層暴力的求解所有可能，然后 取最好的，這個過程非常耗時，大概是 O(N^2 \* K). 然后我看了一位 leetcode[網友](https://leetcode.com/lee215/)的回答, 他的想法是`dp[M][K]means that, given K eggs and M moves，what is the maximum number of floor that we can check.` 我們按照他的思路重新建模：  可以看到右下角的部分根本就不需要計算，從而節省很多時間 ## 關鍵點解析 - dp 建模思路要發生變化, 即 `dp[M][K]means that, given K eggs and M moves，what is the maximum number of floor that we can check.` ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} K * @param {number} N * @return {number} */</span> <span class="hljs-keyword">var</span> superEggDrop = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">K, N</span>) </span>{ <span class="hljs-title">// 不選擇dp[K][M]的原因是dp[M][K]可以簡化操作</span> <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(N + <span class="hljs-params">1</span>) .fill(<span class="hljs-params">0</span>) .map((_) => <span class="hljs-params">Array</span>(K + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>)); <span class="hljs-keyword">let</span> m = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (dp[m][K] < N) { m++; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> k = <span class="hljs-params">1</span>; k <= K; ++k) dp[m][k] = dp[m - <span class="hljs-params">1</span>][k - <span class="hljs-params">1</span>] + <span class="hljs-params">1</span> + dp[m - <span class="hljs-params">1</span>][k]; } <span class="hljs-keyword">return</span> m; }; ``` ```