C++ 中猜数字大还是小 II
c++server side programmingprogramming
假设我们正在玩猜数字游戏。游戏规则如下 −
- 玩家 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 := inf
- 对于从 low 到 high 范围内的 i
- ans := ans 的最小值和(i + cost(low, i – 1, dp) 和 cost(i + 1, high, dp) 的最大值)
- dp[low, high] := ans 并返回 ans
- 实际方法将类似于 −
- 创建一个名为 dp 的二维数组，大小为 (n + 1) x (n + 1)，并用 -1 填充
- return 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
