LeetCode887鸡蛋掉落——dp

谁借莪１个温暖的怀抱￠ 2023-08-17 15:47 100阅读 0赞

## 题目 ##

[题目链接][Link 1]

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。  
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去，如果没有碎可以继续使用。  
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。  
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。  
你的目标是**确切地知道** F 的值是多少。  
无论 F 的初始值如何，请你确定 F 的值的**最小移动次数**是多少？

例如：

输入：K = 1, N = 2
    输出：2

输入：K = 2, N = 100
    输出：14

输入：K = 3, N = 14
    输出：4

**注意**

*  1 <= K <= 100
 *  1 <= N <= 10000

## 思路 ##

### 算法一 ###

**（动态规划）**$O(K\\!N)$

1.  状态$f(i,j)$表示使用$i$个鸡蛋，最大楼层为$j$时，所需要的最小移动次数。
2.  显然初始状态$f(1,j)=j$。对于状态$f(i,j)$，如果枚举上一次测试为楼层$s$，则可以得到如下转移$f(i,j) = min\_\{s=1\}^j(max(f(i-1,s-1),f(i,j-s)) + 1)$，分别表示在第$s$层摔碎和没摔碎。
3.  如果直接枚举$s$，则总的时间复杂度为$O(K\\!N^2)$，无法通过。考虑$f(i-1,s-1)和f(i,j-s)$的大小关系，可以发现，前者随着$s$单调递增，后者单调递减，且每次变化的值最多为1（可证明，略）。所以，如果存在$\{s\}'$使得$f(i-1,s-1) = f(i,j-s)$，则此时$\{s\}'$就是最优的；否则取两者最相近的两个$s$作比较，取最小值。
4.  至此，$s$可以二分解决；总的时间复杂度：$O(K\\!N\\!logN)$。
5.  但进一步可以发现，$s$会随着$j$的增加而增加，即最优决策点$\{s\}'$是随着$j$单调递增的。因为对于固定的$s$，$f(i,j-s)$会随着$j$而增加，这就会造成3中的最优决策点也会向后移动。所以，我们只需在每次移动$j$后，继续从上次的$\{s\}'$向后寻找最优决策点即可。
6.  最终答案是$f(K,N)$

**注意：**在鸡蛋没摔碎时，我们还能用这$i$个鸡蛋在在上面的$j-s$层确定$F$，这里的实验与在第$1~(j-w)$所需的次数是一样的，因为它们的实验方法和步骤都是相同的，只不过这$(j-w)$层在上面罢了。

**时间复杂度**

*  状态数为$O(K\\!N)$，对于每个$i$，寻找最优决策的均摊时间为$O(N)$，故总时间复杂度为$O(K\\!N)$

**C++代码**

1 class Solution {
     2 public:
     3     int superEggDrop(int K, int N) {
     4         int m = K, n = N;
     5         const int maxn = 100 + 10;
     6         const int maxm = 10000 + 10;
     7         int d[maxn][maxm];        //dp[i][j]表示有i颗鹰蛋在j层楼的最少次数
     8         if (m >= ceil(log(n + 1) * 1.0) / log(2.0))
     9             return (int)ceil(log((n + 1) * 1.0) / log(2.0));
    10         else
    11         {
    12             memset(d, 0, sizeof(d));
    13             for (int i = 1; i <= n; i++)  d[1][i] = i;
    14             for (int i = 2; i <= m; i++)
    15             {
    16                 int s = 1;
    17                 for (int j = 1; j <= n; j++)
    18                 {
    19                     d[i][j] = d[i][j - 1] + 1;        //
    20 
    21                     while (s < j && d[i - 1][s] < d[i][j - s - 1])  s++;
    22 
    23                     d[i][j] = min(d[i][j], max(d[i - 1][s - 1], d[i][j - s]) + 1);
    24                     if (s < j)  d[i][j] = min(d[i][j], max(d[i - 1][s], d[i][j - s - 1]) + 1);
    25                 }
    26             }
    27             return d[m][n];
    28         }
    29     }
    30 };

### 算法二 ###

**（动态规划）**$O(KlogN)$

1.  状态$f(i,j)$表示进行$i$次移动，有$j$个鸡蛋，最多可以检查的楼层高度是多少。
2.  初始状态是$f(1,0)=0$，$f(1,j),j \\geq 1$。
3.  先给出转移方程，$f(i,j)= f(i-1,j-1)+f(i-1,j)+1$。假设$n\_1=f(i-1,j-1),n\_2=f(i-1,j)$，我们在第$i$次移动时测试第$n\_1+1$层。
4.  如果测试时鸡蛋碎掉了，则我们可以通过$i-1$次移动和$j-1$个鸡蛋来找到最高不会碎掉的楼层，因为楼层不会超过$n\_1$了；如果鸡蛋没有碎掉，则在此基础上，我们可以使用$i-1$次移动和$j$个鸡蛋，在继续向上检查$n\_2$层，故答案在$\\left \[ 0, n\_1 + n\_2 + 1 \\right \]$范围内，都可以通过$i$次移动、$j$个鸡蛋来找到。
5.  返回最小的$m$满足，$f(m,K) \\geq N$。
6.  这里第一维可以省略，更新时只需要倒序更新即可。

**时间复杂度**

*  最多进行$logN$轮更新，每轮更新需要$O(K)$的时间，故时间复杂度$O(K\\!logN)$。

**C++代码**

1 class Solution {
     2 public:
     3     int superEggDrop(int K, int N) {
     4         vector<int> f(K + 1, 1);
     5         f[0] = 0;
     6         int m = 1;
     7         while (f[K] < N) {
     8             for (int i = K; i >= 1; i--)
     9                 f[i] = f[i] + f[i - 1] + 1;
    10             m++;
    11         }
    12 
    13         return m;
    14     }
    15 };

在URAL OJ上也有这题，只是数据范围有所不同：[Chernobyl’ Eagle on a Roof][Chernobyl_ Eagle on a Roof]

参考链接：

1、[https://www.acwing.com/solution/leetcode/content/579/][https_www.acwing.com_solution_leetcode_content_579]

2、[朱晨光：《优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化][Link 2]

转载于:https://www.cnblogs.com/lfri/p/10350092.html

[Link 1]: https://leetcode-cn.com/problems/super-egg-drop/
[Chernobyl_ Eagle on a Roof]: https://vjudge.net/problem/URAL-1223?tdsourcetag=s_pctim_aiomsg
[https_www.acwing.com_solution_leetcode_content_579]: https://www.acwing.com/solution/leetcode/content/579/
[Link 2]: https://github.com/ericliu859/AcmPaper/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E4%BC%98%E5%8C%96/2004%20-%20%E6%9C%B1%E6%99%A8%E5%85%89%EF%BC%9A%E3%80%8A%E4%BC%98%E5%8C%96%EF%BC%8C%E5%86%8D%E4%BC%98%E5%8C%96%EF%BC%81%E2%80%94%E2%80%94%E4%BB%8E%E3%80%8A%E9%B9%B0%E8%9B%8B%E3%80%8B%E4%B8%80%E9%A2%98%E6%B5%85%E6%9E%90%E5%AF%B9%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95%E7%9A%84%E4%BC%98%E5%8C%96%E3%80%8B/%E6%9C%B1%E6%99%A8%E5%85%89.pdf?tdsourcetag=s_pctim_aiomsg