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