ধরুন আমরা গেস গেম খেলছি। খেলার নিয়ম নিম্নরূপ -
- খেলোয়াড়1 1 থেকে n পর্যন্ত একটি সংখ্যা বেছে নেয়। player2 কে অনুমান করতে হবে যে কোন সংখ্যাটি player1 দ্বারা বাছাই করা হয়েছে।
- যতবার প্লেয়ার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] ফেরত দিন
- উত্তর :=inf
- আমার জন্য নিম্ন থেকে উচ্চ পরিসরে
- উত্তর :=উত্তরের সর্বনিম্ন এবং (i + সর্বোচ্চ খরচ (কম, i – 1, dp) এবং খরচ (i + 1, উচ্চ, dp))
- dp[low, high] :=ans এবং return ans
- প্রকৃত পদ্ধতি হবে − এর মত
- একটি 2d অ্যারে তৈরি করুন যার নাম dp আকারের (n + 1) x (n + 1), এবং এটি -1 দিয়ে পূরণ করুন
- রিটার্ন খরচ (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
