मान लीजिए हमारे पास K अंडे हैं, और N मंजिलों वाली एक इमारत है जो 1 से N तक है। प्रत्येक अंडा कार्य में समान है, और यदि एक अंडा टूट जाता है, तो हम उसे फिर से नहीं गिरा सकते।
एक मंजिल F मौजूद है जो 0 और N के बीच है जैसे कि F से ऊंची किसी भी मंजिल से गिराया गया अंडा टूट जाएगा, और F पर या उससे नीचे गिराया गया अंडा नहीं टूटेगा। प्रत्येक चाल में, हम एक अंडा ले सकते हैं और उसे किसी भी मंजिल X से गिरा सकते हैं। X की रेंज 1 से N है।
हमारा लक्ष्य निश्चितता के साथ F का मान जानना है। तो, न्यूनतम चालों की संख्या क्या होगी जिनकी हमें निश्चितता के साथ F जानने के लिए आवश्यकता होगी, F के प्रारंभिक मान की परवाह किए बिना?
उदाहरण के लिए, यदि K = 2 और N = 6, तो आउटपुट 3 होगा।
हल करने का दृष्टिकोण
हम बाइनरी सर्च अनुकूलन के साथ DP का उपयोग करते हैं:
dp[K][N] = K अंडों और N मंजिलों के लिए न्यूनतम चालें
आधार मामले: N <= 1 या K == 1
प्रत्येक स्थिति के लिए, इष्टतम मंजिल mid खोजने के लिए बाइनरी सर्च करें
left = 1 + solve(K-1, mid-1) (अंडा टूटता है)
right = 1 + solve(K, N-mid) (अंडा नहीं टूटता)
max(left, right) को न्यूनतम करें
बाइनरी सर्च left और right को संतुलित करने के लिए समायोजित करें
उदाहरण
#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, 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);
}
};
int main(){
Solution ob;
cout << (ob.superEggDrop(2,6));
return 0;
}
इनपुट
2, 6
आउटपुट
3
