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