मान लीजिए हम गेस गेम खेल रहे हैं। खेल के नियम इस प्रकार हैं -
- खिलाड़ी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 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- लागत नामक एक विधि बनाएं, जो निम्न, उच्च, दूसरी तालिका डीपी ले रही है
- यदि कम है>=अधिक है, तो 0 लौटें
- अगर dp[low, high] -1 नहीं है, तो dp[low, high] लौटाएं
- उत्तर:=जानकारी
- मेरे लिए निम्न से उच्च श्रेणी में
- उत्तर:=न्यूनतम उत्तर और (i + अधिकतम लागत (कम, i – 1, dp) और लागत (i + 1, उच्च, dp))
- dp[low, high] :=ans and return ans
- वास्तविक विधि इस प्रकार होगी -
- एक 2d सरणी बनाएं जिसे dp आकार (n + 1) x (n + 1) कहा जाता है, और इसे -1 से भरें
- वापसी लागत(1, एन, डीपी)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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