数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 超级鸡蛋掉落问题
假设我们有 K 个鸡蛋，并且有一栋有 N 层楼的建筑物，楼层从 1 到 N。现在每个鸡蛋的功能都相同，如果一个鸡蛋碎了，我们就不能再掉它了。
存在一个楼层 F，其范围在 0 到 N 之间，任何在 F 以上楼层掉落的鸡蛋都会碎，而任何在 F 或 F 以下楼层掉落的鸡蛋都不会碎。在每次移动中，我们都可以取一个鸡蛋，并从任何楼层 X 掉落它。X 的范围在 1 到 N 之间。
我们的目标是确定地知道 F 的值是多少。那么，无论 F 的初始值是多少，我们都需要多少次最少的移动才能确定地知道 F 的值？
因此，如果输入类似于 K = 2 和 N = 6，则输出将为 3。
为了解决这个问题，我们将遵循以下步骤：
定义一个二维数组 dp
定义一个函数 solve()，它将接收 K、N 作为参数。
如果 N <= 1，则：
返回 N
如果 K 等于 1，则：
返回 N
如果 dp[K, N] 不等于 -1，则：
返回 dp[K, N]
ret := N，low := 0，high := N
当 low <= high 时，执行：
left := 1 + solve(K - 1, mid - 1)
right := 1 + solve(K, N - mid)
ret := ret 和 left 与 right 中的最大值之间的最小值
如果 left 等于 right，则：
退出循环
如果 left < right，则
low := mid + 1
否则 high := mid - 1
返回 dp[K, N] = ret
从主方法执行以下操作：
dp := 创建一个 (K + 1) x (N + 1) 的二维数组，并将其填充为 -1
返回 solve(K, N)
让我们看看以下实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> dp;
int solve(int K, int N) {
if (N <= 1)
return N;
if (K == 1)
return N;
if (dp[K][N] != -1)
return dp[K][N];
int ret = N;
int low = 0;
int high = N;
while (low <= high) {
int mid = low + (high - low) / 2;
int left = 1 + solve(K - 1, mid - 1);
int right = 1 + solve(K, N - mid);
ret = min(ret, max(left, right));
if (left == right)
break;
if (left < right) {
low = mid + 1;
} else
high = mid - 1;
}
return dp[K][N] = ret;
}
int superEggDrop(int K, int N) {
dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
return solve(K, N);
}
};
main(){
Solution ob;
cout << (ob.superEggDrop(2,6));
}输入
2, 6
输出
3
更新于: 2020年6月4日
389 次浏览
广告