涉及知识点
暴力、单指针
题目
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 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 <= 104
暴力解法
分析
f 取[0,n]共n+1可能 pre[i]表示i种可能 (j-1)个鸡蛋需要多少回合排除
dp[i]表示i种可能，j个鸡蛋 需要多少回合排除
只有一个鸡蛋，则测试最低的的楼层，如果破了，就得到答案；没破，就排除一种可能。当只一种可能时，不需要尝试，故：j为0时，dp[i]=i-1;
假设有j(j>2)个鸡蛋，假设在某层楼扔下，如果没破，有x种可能；破了，有i-x种可能。
则dp[i] = 1 + max(dp[x],pre[x-1])，x取值[1,i-1]
笨办法枚举x。
时间复杂度
时间复杂度O(knn),超时。
代码
class Solution { public: int superEggDrop(int k, int n) { vector pre(n + 2);//f 取[0,n)共n+1可能 pre[i]表示i种可能 j个鸡蛋需要多少回合排除 for (int i = 0; i <= n+1; i++) { pre[i] = i - 1; } for (int j = 1; j < k; j++) { vector dp(n + 2,1000*100); dp[1] = 0; for (int i = 2; i <= n+1; i++) { for (int x = 1; x < i; x++) { dp[i] = min(dp[i], 1 + max(dp[x], pre[i - x])); } } pre.swap(dp); } return pre.back(); } };
二分
分析
重点考虑：max(dp[x], pre[i - x]));
情况一：dp[x] <= pre[i-x]
x1和x2是合法x，且x1<x2如，则x1被淘汰
证明：因为pre和dp都是单调增加或不变 。 x1<x2 > i-x1 > i-x2 =>pre[i-x1]>=pre[i-x2]
情况二：dp[x] > pre[i-x]
同理：只需要考虑最小的x
情况一最大的x是xLeft,情况二最小的x是xRight，则xRightxLeft+1
故只需求xRight，注意:xRight可能不存在
情况二符合条件，多个符合条件返回第一个，用左开右闭空间二分。
时间复杂度
O(nklogn)。枚举鸡蛋数时间复杂度O(k)，枚举可能数时间复杂度O(n)，计算xRight时间复杂度O(logn)。
代码
class Solution { public: int superEggDrop(int k, int n) { vector<int> pre(n + 2);//f 取[0,n)共n+1可能 pre[i]表示i种可能 j个鸡蛋需要多少回合排除 for (int i = 0; i <= n + 1; i++) { pre[i] = i - 1; } for (int j = 1; j < k; j++) { vector<int> dp(n + 2, 1000 * 100); dp[0] = dp[1] = 0; for (int i = 2; i <= n + 1; i++) { int left = 0, right = i ; while (right - left > 1) { const auto mid = left + (right - left) / 2; if (dp[mid] > pre[i - mid]) { right = mid; } else { left = mid; } } if (right < i ) { auto x = right; dp[i] = min(dp[i], 1 + max(dp[x], pre[i - x])); } if (right >= 2) { auto x = right-1; dp[i] = min(dp[i], 1 + max(dp[x], pre[i - x])); } } pre.swap(dp); } return pre.back(); } };
单指针
随着i的增加，xRight只会增加或变大。每个j，xRight的时间复杂度是O(n)，总时间复杂度是O(kn)。
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int res = 0; { res = Solution().superEggDrop(2, 6); Assert(3, res); } { res = Solution().superEggDrop(3, 14); Assert(4, res); } { res = Solution().superEggDrop(10, 100); Assert(7, res); } { res = Solution().superEggDrop(9, 89); Assert(7, res); } { res = Solution().superEggDrop(100, 10000); Assert(14, res); }
//CConsole::Out(res);
}
2023年1月7号版
class Solution { public: int superEggDrop(int k, int n) { int iMaxStep = MaxStep(k,n); vector preDp(iMaxStep + 1); int iMinSetp = INT_MAX; for (int i = 0; i <= iMaxStep; i++) { preDp[i] = i+1; if (i + 1 -1 >= n) { iMinSetp = i; } } while (–k) { vector dp(iMaxStep + 1); dp[0] = 1; for (int i = 1; i <= iMaxStep; i++) { const int tmp = dp[i - 1] + preDp[i - 1]; dp[i] = tmp; if (tmp > n) { iMinSetp = i; break; } } preDp.swap(dp); } return iMinSetp; } int MaxStep(int k, int n)const { int iOpeNum = 0; int iCan = 1;//iOpeNum回合可以判定胡楼层 for (int i = 2; i < 10000; i++) { for (int j = 0; j < k; j++) { if (iCan > n) { return iOpeNum; } iCan /= (i - 1); iCan *= i; iOpeNum++; } } return 100; } };
2023年1月8号版
枚举各回合，能判断多少种可能。
class Solution{ public: int superEggDrop(int k, int n) { //dp[j] 表示iStep回合，j个鸡蛋能表示的可能 vector pre(k + 1,2); pre[0] = 1; if (2 > n) { return 1; } for (int iStep = 2; iStep < 20000; iStep++) { vector dp(k + 1, 1); for (int j = 1; j <= k; j++) { dp[j] = pre[j] + pre[j - 1]; if (dp[j] > n) { return iStep; } } pre.swap(dp); } return -1; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
