मान लीजिए हमने K अंडे दिए हैं, और हमारे पास 1 से N तक N मंजिलों वाली एक इमारत है। अब प्रत्येक अंडा कार्य में समान है, और यदि कोई अंडा टूटता है, तो हम उसे दोबारा नहीं गिरा सकते।
0 और N के बीच एक मंजिल F मौजूद है, ताकि F से ऊंची मंजिल पर गिरा कोई भी अंडा टूट जाए, और मंजिल F पर या नीचे गिरा हुआ कोई भी अंडा नहीं टूटेगा। प्रत्येक चाल में, हम एक अंडा ले सकते हैं और उसे किसी भी मंजिल X से गिरा सकते हैं। X 1 से N की सीमा में है।
हमारा लक्ष्य निश्चित रूप से यह जानना है कि F का मान क्या है। तो, चालों की न्यूनतम संख्या क्या होगी जो हमें निश्चित रूप से जानने के लिए आवश्यक है कि F क्या है, F के प्रारंभिक मान की परवाह किए बिना?
इसलिए, यदि इनपुट K =2 और N =6 जैसा है, तो आउटपुट 3 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक 2डी सरणी डीपी परिभाषित करें
-
एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें K, N,
लगेगा -
अगर एन <=1, तो -
-
वापसी एन
-
-
यदि K 1 के समान है, तो -
-
वापसी एन
-
-
अगर dp[K, N] -1 के बराबर नहीं है, तो -
-
वापसी डीपी [के, एन]
-
-
रिट:=एन, लो:=0, हाई:=एन
-
जबकि कम <=उच्च, करें −
-
बाएँ :=1 + हल करें(K-1, मध्य -1)
-
दाएं:=1 + हल करें (के, एन - मध्य)
-
ret :=न्यूनतम रिट और अधिकतम बाएँ और दाएँ
-
यदि बायाँ दाएँ के समान है, तो -
-
लूप से बाहर आएं
-
-
अगर बाएं <दाएं, तो:
-
कम :=मध्य + 1
-
-
अन्यथा उच्च :=मध्य - 1
-
-
वापसी डीपी [के, एन] =सेवानिवृत्त
-
मुख्य विधि से निम्न कार्य करें -
-
dp :=एक 2D सरणी बनाएं (K + 1) x (N + 1), इसे -1 से भरें
-
वापसी हल (के, एन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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
