数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 实现猜数字大小 II
假设我们正在玩猜数字游戏。游戏规则如下：
- 玩家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
- 对于 i 从 low 到 high 的范围
- 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
- 返回 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
更新于: 2020年4月29日
260 次查看
广告