<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 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/) 這是一道典型的動態規劃題目,但是又和一般的動態規劃不一樣。 拿題目給的例子為例,兩個雞蛋,六層樓,我們最少扔幾次? ![](https://img.kancloud.cn/ae/51/ae5157973cddff2fdefe0e79b4c6b121_571x455.jpg) 一個符合直覺的做法是,建立 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.` 我們按照他的思路重新建模: ![](https://img.kancloud.cn/95/55/955516a497db9ac6cab265e95de9f8d9_832x356.jpg) 可以看到右下角的部分根本就不需要計算,從而節省很多時間 ## 關鍵點解析 - 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; }; ``` ```
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看