C++でのスーパーエッグドロップ

K個の卵を与え、1からNまでのN階の建物があるとします。これで、各卵の機能は同じになり、卵が壊れた場合、再び落とすことはできません。

Fより高い階に落とされた卵は壊れず、F階以下に落とされた卵は壊れないように、0からNの間のF階が存在します。それぞれの動きで、私たちは卵を取り、それを任意のフロアXから落とすことができます。Xは1からNの範囲にあります。

私たちの目標は、Fの値が何であるかを確実に知ることです。では、Fの初期値に関係なく、Fが何であるかを確実に知る必要がある最小移動数はいくつになるでしょうか？

したがって、入力がK=2およびN=6のような場合、出力は3になります。

これを解決するには、次の手順に従います-

• 1つの2D配列dpを定義します

• 関数solve（）を定義します。これには、K、N、

  が必要です。

• N <=1の場合、-

  • Nを返す

• Kが1と同じ場合、-

  • Nを返す

• dp [K、N]が-1に等しくない場合、-

  • dp [K、N]

    を返します

• ret：=N、low：=0、high：=N

  • 低い<=高い間、実行-

  • 左：=1 +solve（K-1、mid-1）

  • 右：=1 + Solve（K、N-mid）

  • ret：=retの最小値と左右の最大値

  • 左が右と同じ場合、-

    • ループから出てきます

  • 左<右の場合：

    • 低：=中+ 1

  • それ以外の場合は高い：=中程度-1

• dp [K、N] =ret

  を返します

• 主な方法を確認するには、次のようにします-

• dp：=1つの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