374 猜数字大小
题目描述： 我们正在玩一个猜数字游戏。 游戏规则如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：-1 : 我的数字比较小；1 : 我的数字比较大；0 : 恭喜！你猜对了！
思路： 二分猜数字。
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
int ABC(int n);
class Solution {
public:
int guessNumber(int n) {
long long low = 1, high = n, mid = 0;
int ans = 0;
while(low <= high) {
mid = (low + high) / 2;
if(guess(mid) <= 0) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
};
375 猜数字大小2
题目描述： 我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
思路： 区间动态规划。
题目理解： 给你一个n，他可能实际的数字(即我选的数)是1-n中的任意一个(记为i)，对于每一个i，有很多种猜法，有一个答案花费是最小的。我们对于每一个i都有一个最小花费，那么答案就是所有i对应的最小花费的最大值。
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n+2, vector<int>(n+2, 100000000));
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= i; j++){
dp[i][j] = 0;
}
}
for(int len = 2; len <= n; len++) {
for(int L = 1; L + len - 1 <= n; L++) {
int R = L + len - 1;
for(int mid = L; mid <= R; mid++)
dp[L][R] = min(dp[L][R], max(dp[L][mid - 1], dp[mid + 1][R]) + mid);
}
}
return dp[1][n];
}
};