C ++中的超级鸡蛋滴
假设我们给了K个鸡蛋，并且我们有一个N层从1到N的建筑物。现在每个鸡蛋的功能是相同的，并且如果一个鸡蛋破裂了，我们就不能再次丢弃它。
存在一个介于0到N之间的F层，这样，落在F层以上的任何鸡蛋都不会破裂，而落在F层以下或F层以下的任何鸡蛋都不会破裂。在每一步中，我们可能会拿一个鸡蛋并将其从任意楼层X放下。X的范围是1到N。
我们的目标是确定F的值。那么，无论F的初始值如何，我们需要确定地知道F是多少的最小移动次数是多少？
因此，如果输入为K=2且N=6，则输出为3。
为了解决这个问题，我们将遵循以下步骤-
定义一个2D数组dp
定义一个函数solve()，它将取K，N，
如果N<=1，则-
返回N
如果K等于1，则-
返回N
如果dp[K，N]不等于-1，则-
返回dp[K，N]
ret：=N，低：=0，高：=N
低：=中+1
从循环中出来
当低<=高时，执行-
左：=1+求解（K-1，中-1）
右：=1+Solve(K,N-mid)
ret：=ret的最小值和left和right的最大值
如果左与右相同，则-
如果左<右，则：
否则高：=中-1
返回dp[K，N]=ret
Frm主要方法执行以下操作-
dp：=创建一个2D数组（K+1）x（N+1），并用-1填充
返回求解(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