887鸡蛋掉落

心已赠人 2023-02-25 02:05 171阅读 0赞

一、前言

分类：动态规划。

问题来源LeetCode 887 难度：困难。

问题链接：https://leetcode-cn.com/problems/super-egg-drop/

二、题目

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

示例1：

  1. 输入：K = 1, N = 2
  2. 输出：2
  3. 解释：
  4. 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
  5. 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
  6. 如果它没碎，那么我们肯定知道 F = 2 。
  7. 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：

  1. 输入：K = 2, N = 6
  2. 输出：3

示例 3：

  1. 输入：K = 3, N = 14
  2. 输出：4

提示：

  1. 1 <= K <= 100
  2. 1 <= N <= 10000

三、题意分析

题目看了半天没整明白T_T。最后一句是关键，你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F的值的最小移动次数是多少？

可以这样理解：无论F不管是多少，至少要丢多少次鸡蛋？

也可以这样理解：最坏情况下，你至少要扔几次鸡蛋？

四、思路分析

思路来源网上，按照自己的理解进行整理一下。

参考：

  1. https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution-2/
  2. https://leetcode-cn.com/problems/super-egg-drop/solution/887-by-ikaruga/

4.1 第一类解题思路：动态规划 + 二分搜索

我们可以考虑使用动态规划来做这道题，状态可以表示成 (K,N)，其中 K 为鸡蛋数，N 为楼层数。当我们从第 X 楼扔鸡蛋的时候：

  • 如果鸡蛋不碎，那么状态变成 (K, N-X)，即我们鸡蛋的数目不变，但答案只可能在上方的 N−X 层楼了。也就是说，我们把原问题缩小成了一个规模为 (K,N−X) 的子问题；
  • 如果鸡蛋碎了，那么状态变成 (K−1,X−1)，即我们少了一个鸡蛋，但我们知道答案只可能在第 XX 楼下方的 X−1 层楼中了。也就是说，我们把原问题缩小成了一个规模为(K−1,X−1) 的子问题。

这样一来，我们定义 dp(K, N) 为在状态 (K,N) 下最少需要的步数。根据以上分析我们可以列出状态转移方程：

20200709224400442.png

这个状态转移方程是如何得来的呢？对于 dp(K, N) 而言，我们像上面分析的那样，枚举第一个鸡蛋扔在的楼层数 X。由于我们并不知道真正的 F 值，因此我们必须保证 鸡蛋碎了之后接下来需要的步数 和 鸡蛋没碎之后接下来需要的步数 二者的 最大值 最小，这样就保证了在 最坏情况下（也就是无论 F 的值如何） dp(K, N) 的值最小。如果能理解这一点，也就能理解上面的状态转移方程，即最小化max(dp(K-1, X-1), dp(K, N-X))。

复杂度分析

时间复杂度：O(K∗NlogN)。我们需要计算 O(K∗N) 个状态，每个状态计算时需要 O(logN) 的时间进行二分搜索。

空间复杂度：O(K∗N)。我们需要 O(K∗N) 的空间存储每个状态的解。

4.2 第二类解题思路：动态规划，问题转换+逆向推到

N 和 F 的关系

  1. N 的定义：使用一栋从 1 到 N 共有 N 层楼的建筑
  2. F 的定义：满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破
  3. 因此得知，F 比 N 多一个 0 层

问题转换

  1. 将问题从： N 个楼层，有 K 个蛋，求最少要扔 T 次，才能保证当 F 无论是 0 <= F <= N 中哪个值，都能测试出来
  2. 转变为：有 K 个蛋，扔 T 次，就可以确定 F 的个数，然后得出 N 个楼层

递推公式

  1. F(K,T) 记为有K个鸡蛋，T次扔鸡蛋的机会，可以测试的最大楼层数；
  2. 当扔一个鸡蛋，产生的效果是：【蛋碎了减 1 个，机会减 1 次】 + 【蛋没碎，机会减 1 次】
  3. 通过步骤2，可以获取到递推公式： F(K, T) = F(K - 1, T - 1) + F(K, T - 1)

临界条件

  1. 当只有一个鸡蛋，只能从1楼开始往上扔直到鸡蛋破碎，其中还有一个0楼，也就是一个鸡蛋可以测试最大楼层=T+1，F(1, T) = T + 1。
  2. 只有一次扔鸡蛋的机会，等价于只有一个鸡蛋且只能扔一次 F(K+1) = 2。也可以这样理解，只有能扔一次那就从1楼扔下去，破了可以确定0层不会破，1层会破F=2；不破，可以确定0层和1层都不会破F=2，也就是 F(K+1) = 2。

图：F(K, T)，F(K, T)为可以确定的楼层数，包含0层，也就是题意中 N-1 = F(K, T)。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70

五、解决方法

提供了四种解决方法。

方法一：第一类，动态规划 + 二分搜索。时间复杂度：O(K∗NlogN)，空间复杂度：O(K∗N)。

方法二： 第二类，自顶向下通过递归解决。时间复杂度：O(K∗N)，空间复杂度：O(1)。

  1. class Solution_2
  2. {
  3. public:
  4.     int superEggDrop(int K, int N)
  5.     {
  6.         int T = 1;
  7.         while (calcF(K, T) < N + 1) T++;
  8.         return T;
  9.     }
  11.     int calcF(int K, int T)
  12.     {
  13.         if (T < 1 && K < 1) return 0;    // T 和 K 不能都小于1
  14.         if (K == 1) return T + 1;        // 只有一个鸡蛋，从一楼开始往扔，最多确定楼层为T+1
  15.         if (T == 1) return 2;            // 只扔一次那就从1楼扔下去，可以确定0层和1层
  16.         //if (T == 1 || K == 1) return T + 1;
  17.         return calcF(K - 1, T - 1) + calcF(K, T - 1);
  18.     }
  19. };

代码解析：

  • calcF(K, T)，计算f(K，T)值也就是可以确定的楼层数，由于K是固定的，结果随T增加而增加，当可以确定的楼层数大于或等N+1，T即为所求，N+1是因为包含了0层。

方法三：将方法二转为自底向上，非递归解决。时间复杂度：O(K∗N)，空间复杂度：O(2N)。

  1. class Solution_3
  2. {
  3. public:
  4.     int superEggDrop(int K, int N)
  5.     {
  6.         if (K <= 0 || N <= 0)
  7.             return 0;
  9.         vector<vector<int>> dp(2, vector<int>(K+1, 2));
  10.         vector<int>* pre = &dp[0];
  11.         vector<int>* cur = &dp[1];
  13.         for (int i = 2; i <= N; ++i)
  14.         {
  15.             (*cur)[1] = i + 1;
  16.             for (int j = 2; j <= K; ++j)
  17.                 (*cur)[j] = (*pre)[j - 1] + (*pre)[j];
  19.             if ((*cur)[K] > N)
  20.                 return i;
  22.             swap(cur, pre);
  23.         }
  24.         return 1;
  25.     }
  26. };

辅助空间说明，图形观察如下， F(K, T) = F(K - 1, T - 1) + F(K, T - 1)，上一层结果觉得下一次值，只需要用2*(K+1)个辅助空间即可。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1

方法四：对方法三空间进行优化。时间复杂度：O(K∗N)，空间复杂度：O(N)。

  1. class Solution_4
  2. {
  3. public:
  4.     int superEggDrop(int K, int N)
  5.     {
  6.         if (K <= 0 || N <= 0)
  7.             return 0;
  9.         vector<int> dp(K+1,2);
  10.         for (int i = 2; i <= N; ++i)
  11.         {
  12.             for (int j = K; j >= 2; --j)
  13.                 dp[j] += dp[j - 1];
  15.            dp[1] = i + 1;
  16.            if (dp[K] > N)
  17.                return i;
  18.         }
  20.         return 1;
  21.     }
  22. };

继续观察这个图发现，从后完前计算辅助空间中数据，只需要一行辅助空间就可以了。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2

六、总结

  1. 正确理解题意；
  2. 两类解题思路都是讲大问题拆分成小问题；
  3. 尤其是第二类解题思路，当扔一下鸡蛋会产生两个结果F(K-1,T-1)和F(K,T-1)，这个和《跳台阶》问题很类似；
  4. 动态规划问题最最最重要的是问题拆分（状态转换）找到递推公式。

七、完整代码

  1. //==========================================================================
  2. /*
  3. * @file    : 887_SuperEggDrop.h
  4. * @blogs   : 
  5. * @author  : niebingyu
  6. * @date    : 2020/07/08
  7. * @title   : 887.鸡蛋掉落
  8. * @purpose : 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。
  9. *             每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
  10. *             你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
  11. *             每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
  12. *             你的目标是确切地知道 F 的值是多少。
  13. *             无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
  14. *
  15. * 示例 1：
  16. * 输入：K = 1, N = 2
  17. * 输出：2
  18. * 解释：
  19. * 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
  20. * 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
  21. * 如果它没碎，那么我们肯定知道 F = 2 。
  22. * 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
  23. *
  24. * 示例 2：
  25. * 输入：K = 2, N = 6
  26. * 输出：3
  27. *
  28. * 示例 3：
  29. * 输入：K = 3, N = 14
  30. * 输出：4
  31. *  
  32. * 提示：
  33. * 1 <= K <= 100
  34. * 1 <= N <= 10000
  35. *
  36. * 来源：力扣（LeetCode）
  37. * 难度：困难
  38. * 链接：https://leetcode-cn.com/problems/super-egg-drop
  39. */
  40. //==========================================================================
  41. #pragma once
  42. #include <iostream>
  43. #include <vector>
  44. #include <unordered_map>
  45. #include <algorithm>
  46. using namespace std;
  48. #define NAMESPACE_SUPEREGGDROP namespace NAME_SUPEREGGDROP {
  49. #define NAMESPACE_SUPEREGGDROPEND }
  50. NAMESPACE_SUPEREGGDROP
  52. // 方法一
  53. // 动态规划 + 二分搜索
  54. // 递推公式
  55. // dp(K, N) = 1 + min(max(dp(K−1, X−1), dp(K, N−X)))
  56. //              1<=x<=N
  57. class Solution_1 
  58. {
  59. public:
  60.     int superEggDrop(int K, int N) 
  61.     {
  62.         return dp(K, N);
  63.     }
  65. private:
  66.     unordered_map<int, int> memo;
  67.     int dp(int K, int N) 
  68.     {
  69.         if (memo.find(N * 100 + K) == memo.end()) 
  70.         {
  71.             int ans;
  72.             if (N == 0) ans = 0;
  73.             else if (K == 1) ans = N;
  74.             else 
  75.             {
  76.                 int lo = 1, hi = N;
  77.                 while (lo + 1 < hi) 
  78.                 {
  79.                     int x = (lo + hi) / 2;
  80.                     int t1 = dp(K-1, x-1);
  81.                     int t2 = dp(K, N-x);
  83.                     if (t1 < t2) lo = x;
  84.                     else if (t1 > t2) hi = x;
  85.                     else lo = hi = x;
  86.                 }
  88.                 ans = 1 + min(max(dp(K-1, lo-1), dp(K, N-lo)),
  89.                     max(dp(K-1, hi-1), dp(K, N-hi)));
  90.             }
  92.             memo[N * 100 + K] = ans;
  93.         }
  95.         return memo[N * 100 + K];
  96.     }
  97. };
  99. // 方法二：动态规划，问题转换+逆向推到
  100. // 自顶向下，递归解决
  101. // F(K, T) = F(K - 1, T - 1) + F(K, T - 1)
  102. // F(1, T) = T + 1
  103. // F(K, 1) = 2
  104. /*
  105. * N 和 F 的关系
  106. * N 的定义：使用一栋从 1 到 N 共有 N 层楼的建筑
  107. * F 的定义：满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破
  108. * 因此得知，F 比 N 多一个 0 层
  109. *
  110. * 问题转换
  111. * 将问题从： N 个楼层，有 K 个蛋，求最少要扔 T 次，才能保证当 F 无论是 0 <= F <= N 中哪个值，都能测试出来
  112. * 转变为：有 K 个蛋，扔 T 次，求可以确定 F 的个数，然后得出 N 个楼层
  113. */
  114. class Solution_2
  115. {
  116. public:
  117.     int superEggDrop(int K, int N)
  118.     {
  119.         int T = 1;
  120.         while (calcF(K, T) < N + 1) T++;
  121.         return T;
  122.     }
  124.     int calcF(int K, int T)
  125.     {
  126.         if (T < 1 && K < 1) return 0;    // T 和 K 不能都小于1
  127.         if (K == 1) return T + 1;        // 只有一个鸡蛋，从一楼开始往扔，最多确定楼层为T+1
  128.         if (T == 1) return 2;            // 只扔一次那就从1楼扔下去，可以确定0层和1层
  129.         //if (T == 1 || K == 1) return T + 1;
  130.         return calcF(K - 1, T - 1) + calcF(K, T - 1);
  131.     }
  132. };
  134. // 方法三：动态规划，问题转换+逆向推到
  135. // 自底向上，非递归解决
  136. //F(K, T) = F(K - 1, T - 1) + F(K, T - 1)
  137. //F(1, T) = T + 1
  138. //F(K, 1) = 2
  139. class Solution_3
  140. {
  141. public:
  142.     int superEggDrop(int K, int N)
  143.     {
  144.         if (K <= 0 || N <= 0)
  145.             return 0;
  147.         vector<vector<int>> dp(2, vector<int>(K+1, 2));
  148.         vector<int>* pre = &dp[0];
  149.         vector<int>* cur = &dp[1];
  151.         for (int i = 2; i <= N; ++i)
  152.         {
  153.             (*cur)[1] = i + 1;
  154.             for (int j = 2; j <= K; ++j)
  155.                 (*cur)[j] = (*pre)[j - 1] + (*pre)[j];
  157.             if ((*cur)[K] > N)
  158.                 return i;
  160.             swap(cur, pre);
  161.         }
  162.         return 1;
  163.     }
  164. };
  166. // 方法四：动态规划，问题转换+逆向推到
  167. // 自底向上，非递归解决，对方法三空间优化
  168. // F(K, T) = F(K - 1, T - 1) + F(K, T - 1)
  169. // F(1, T) = T + 1
  170. // F(K, 1) = 2
  171. class Solution_4
  172. {
  173. public:
  174.     int superEggDrop(int K, int N)
  175.     {
  176.         if (K <= 0 || N <= 0)
  177.             return 0;
  179.         vector<int> dp(K+1,2);
  180.         for (int i = 2; i <= N; ++i)
  181.         {
  182.             for (int j = K; j >= 2; --j)
  183.                 dp[j] += dp[j - 1];
  185.            dp[1] = i + 1;
  186.            if (dp[K] > N)
  187.                return i;
  188.         }
  190.         return 1;
  191.     }
  192. };
  194. 以下为测试代码//
  195. // 测试 用例 START
  196. void test(const char* testName, int K, int N, int expect)
  197. {
  198.     Solution_1 s1;
  199.     int result1 = s1.superEggDrop(K, N);
  201.     Solution_2 s2;
  202.     int result2 = s2.superEggDrop(K, N);
  204.     Solution_3 s3;
  205.     int result3 = s3.superEggDrop(K, N);
  207.     Solution_4 s4;
  208.     int result4 = s4.superEggDrop(K, N);
  210.     if (expect == result1 && expect == result2 && expect == result3 && expect == result4)
  211.         cout << testName << ", solution passed." << endl;
  212.     else
  213.         cout << testName << ", solution failed. expect: "<< expect
  214.         << ", result1: "<< result1 << ", result2: " << result2
  215.         << ", result3: "<< result3 << ", result4: " << result4 << endl;
  216. }
  218. // 测试用例
  219. void Test1()
  220. {
  221.     int K = 1;
  222.     int N = 1;
  223.     int expect = 1;
  225.     test("Test1()", K, N, expect);
  226. }
  228. void Test2()
  229. {
  230.     int K = 1;
  231.     int N = 2;
  232.     int expect = 2;
  234.     test("Test2()", K, N, expect);
  235. }
  237. void Test3()
  238. {
  239.     int K = 1;
  240.     int N = 3;
  241.     int expect = 3;
  243.     test("Test3()", K, N, expect);
  244. }
  246. void Test4()
  247. {
  248.     int K = 3;
  249.     int N = 2;
  250.     int expect = 2;
  252.     test("Test4()", K, N, expect);
  253. }
  255. void Test5()
  256. {
  257.     int K = 3;
  258.     int N = 14;
  259.     int expect = 4;
  261.     test("Test5()", K, N, expect);
  262. }
  264. void Test6()
  265. {
  266.     int K = 3;
  267.     int N = 92;
  268.     int expect = 8;
  270.     test("Test6()", K, N, expect);
  271. }
  273. void Test7()
  274. {
  275.     int K = 7;
  276.     int N = 501;
  277.     int expect = 9;
  279.     test("Test7()", K, N, expect);
  280. }
  281. NAMESPACE_SUPEREGGDROPEND
  282. // 测试 用例 END
  283. //
  285. void SuperEggDrop_Test()
  286. {
  287.     NAME_SUPEREGGDROP::Solution_2 s2;
  288.     for (int t = 10; t <= 20; ++t)
  289.     {
  290.         for (int k = 1; k <= 9; ++k)
  291.         {
  292.             cout << s2.calcF(k, t) << " ";
  293.         }
  294.         cout << endl;
  295.     }
  296.     cout << endl;
  298.     NAME_SUPEREGGDROP::Test1();
  299.     NAME_SUPEREGGDROP::Test2();
  300.     NAME_SUPEREGGDROP::Test3();
  301.     NAME_SUPEREGGDROP::Test4();
  302.     NAME_SUPEREGGDROP::Test5();
  303.     NAME_SUPEREGGDROP::Test6();
  304.     NAME_SUPEREGGDROP::Test7();
  305. }

执行结果：

20200709225038676.png

八、拓展一，加深理解

找出N=110，K=5，最优扔鸡蛋楼层可能的一种情况，并进行分析？

  1. 先在K=5，中找最小大于110的值，结果是K=5，T=7；
  2. 最优的结果并不是一种，这里提供其中一种扔鸡蛋的方法，在第N+1 = 57，也就是第56层扔一个鸡蛋；
  3. 如果鸡蛋没有破，此时K=5，T=6，破在N=57-109层中查找，57-109层和0-42层是等价的，f(K=5,T=6)最大可以查找63层（0-62），查找0-42层是没有问题的；
  4. 如果鸡蛋破了，此时K=4，T=6，此时刚好可以查找57层（0-56）满足要求；
  5. 后续重复步骤1直到K=1或者T=1。

这里我们可以进一步理解递推公式： F(K, T) = F(K - 1, T - 1) + F(K, T - 1)

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3

#

九、拓展二，面试问题

  1. 有 2 个蛋，用一座 100 层的楼，要使用最少次数测试出蛋几层会碎（F）。
  2. 问第一次应该从几层扔。注意不包含0层。

这个问题曾经也遇到过，那时候一头雾水。T.T

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4

从图可以直观的看到第一次扔是在第14层。(1+1)+2+3+4+…+14 = 106

发表评论

表情：
评论列表 （有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

    相关 鸡蛋掉落

    题目 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F

    淡淡的烟草味﹌淡淡的烟草味﹌/ 0 赞/ 329 阅读