গেস গেম: প্লেয়ার ১, ১ থেকে n পর্যন্ত নম্বর পিক করে। প্লেয়ার ২ গেস করে। ভুল গেসে প্লেয়ার ১ বলে হাইওয়ার/লোয়ার। গেস x-এ ভুল হলে $x টাকা দিতে হয়। ন্যূনতম খরচে গ্যারান্টি সহ সঠিক নম্বর পাওয়ার খরচ বের করতে হবে।
উদাহরণ: n=8 → ১২।
সমাধানের ধাপসমূহ
- DP:
cost(low, high)= রেঞ্জ [low, high]-এ গ্যারান্টি সহ জয়ের ন্যূনতম খরচ। - বেস: low >= high → ০।
- প্রতিটি i = low..high ট্রাই করুন: খরচ = i + max(cost(low,i-1), cost(i+1,high))।
- ন্যূনতম খরচ নিন। মেমোরাইজেশন ব্যবহার করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
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;
}
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
return cost(1, n, dp);
}
};
int main() {
Solution ob;
cout << ob.getMoneyAmount(8);
}
ইনপুট
8
আউটপুট
12
