मान लीजिए हम गेस गेम खेल रहे हैं। खेल के नियम इस प्रकार हैं:
- खिलाड़ी1 1 से n तक एक संख्या चुनता है। खिलाड़ी2 को अनुमान लगाना है कि खिलाड़ी1 द्वारा कौन सी संख्या चुनी गई है।
- हर बार खिलाड़ी2 गलत अनुमान लगाता है, खिलाड़ी1 बताएगा कि चुनी गई संख्या अधिक है या कम।
हालांकि, जब कोई खिलाड़ी एक विशेष संख्या x का अनुमान लगाता है, और दूसरा खिलाड़ी गलत अनुमान लगाता है, तो दूसरे खिलाड़ी को $x का भुगतान करना पड़ता है। खेल समाप्त होगा जब खिलाड़ी2 को सही उत्तर मिल जाएगा।
उदाहरण के लिए, यदि n = 10, और खिलाड़ी1 ने 8 लिया है:
- पहले राउंड में, खिलाड़ी2 संख्या 5 बताता है, जो गलत है, वास्तविक संख्या अधिक है, तो वह $5 देगा
- दूसरे राउंड में, खिलाड़ी2 संख्या 7 बताता है, जो गलत है, वास्तविक संख्या अधिक है, तो वह $7 देगा
- तीसरे राउंड में, खिलाड़ी2 संख्या 9 बताता है, जो गलत है, वास्तविक संख्या कम है, तो वह $9 देगा
अब खेल समाप्त होता है। कुल दिया गया पैसा $5 + $7 + $9 = $21 है।
हल करने के चरण
- cost नामक एक विधि बनाएं, जो low, high, और dp टेबल लेती है
- यदि low >= high, तो 0 वापस करें
- यदि dp[low][high] != -1, तो dp[low][high] वापस करें
- ans := अनंत
- i को low से high तक लूप करें
- ans := min(ans, i + max(cost(low, i-1, dp), cost(i+1, high, dp)))
- dp[low][high] := ans और ans वापस करें
- वास्तविक विधि:
- (n+1) x (n+1) आकार का एक 2D सरणी dp बनाएं, और इसे -1 से भरें
- cost(1, n, dp) वापस करें
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: int cost(int low, int high, vector < vector <int> >& dp){ if(low >= high)return 0; if(dp[low][high] != -1)return dp[low][high]; int ans = INT_MAX; for(int i = low; i <= high; i++){ ans = min(ans, i + max(cost(low, i - 1, dp), cost(i + 1, high, dp))); } return dp[low][high] = ans; } int getMoneyAmount(int n) { vector < vector <int> > dp(n + 1, vector <int> (n + 1, -1)); return cost(1, n, dp); } }; int main() { Solution ob1; cout << ob1.getMoneyAmount(8) << endl; return 0; }इनपुट
8
आउटपुट
12