在C ++中猜测数字的高低II
假设我们正在玩猜猜游戏。游戏的规则如下-
Player1选择一个从1到n的数字。玩家2必须猜测玩家1选择了哪个号码。
每当玩家2猜错时，玩家1都会告诉您所选择的数字是更高还是更低。
但是，当一个玩家猜出一个特定的数字x时，另一个玩家猜错了，另一个玩家必须支付$x。当player2得到正确答案后，游戏将结束。
例如，如果n=10，而玩家1拿了8
在第一轮中，player2告诉数字是5，那是错误的，实际数字更高，那么他会给$5
在第二轮中，player2告诉数字是7，那是错误的，实际数字更高，那么他会给$7
在第三轮中，player2告诉数字为9，那是错误的，实际数字较低，那么他会给$9
现在游戏结束。因此，给定的总金额为$5+$7+$9=$21。
为了解决这个问题，我们将遵循以下步骤-
创建一个称为成本的方法，即低，高，另一种表dp
如果低>=高，则返回0
如果dp[low，high]不为-1，则返回dp[low，high]
ans：=inf
对于我范围从低到高
ans：=ans的最小值和（i+最大成本（low，i–1，dp）和cost（i+1，高，dp））
dp[low，high]：=ans并返回ans
实际的方法将是-
制作一个称为dp的2d数组，其大小为（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