375 Guess Number Higher or Lower II 猜数字大小 II
Description:
We are playing the Guessing Game. The game will work as follows:
I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
Example:
Example 1:
Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
- If this is my number, your total is $0. Otherwise, you pay $7.
- If my number is higher, the range is [8,10]. Guess 9.
- If this is my number, your total is $7. Otherwise, you pay $9.
- If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
- If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
- If my number is lower, the range is [1,6]. Guess 3.
- If this is my number, your total is $7. Otherwise, you pay $3.
- If my number is higher, the range is [4,6]. Guess 5.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
- If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
- If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
- If my number is lower, the range is [1,2]. Guess 1.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.
Example 2:
Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.
Example 3:
Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
- If this is my number, your total is
1.
- If my number is higher, it must be 2. Guess 2. Your total is
1.
- If this is my number, your total is
Constraints:
1 <= n <= 200
题目描述:
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例 :
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
思路:
动态规划
dp[i][j]表示落入 [i, j]时, 需要支付的最小的钱的数量
比如 dp[1][1]表示当前区间为 [1, 1], 这时只用猜 1必定猜中, 所以 dp[1][1] = 0
类似的有 dp[i][i] = 0
dp[2][3]表示当前区间为 [2, 3], 这时如果答案是 2, 猜 2不用给钱, 猜 3需要给 3块, 如果答案是 3, 猜 2给 2块, 猜 3不用给, 那么选择猜 2, 最少支付 2块一定猜中
动态转移方程 dp[i][j] = max(dp[i][k - 1], dp[k + 1][j]) + k, i < k < j, dp[i][i] = 0
时间复杂度O(n ^ 3), 空间复杂度O(n ^ 2)
代码:
C++:
class Solution
{
public:
int getMoneyAmount(int n)
{
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int i = n; i > 0; i--) for (int j = i + 1; j < n + 1; j++)
{
dp[i][j] = INT_MAX;
for (int k = i; k < j + 1; k++) dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k);
}
return dp[1][n];
}
};
Java:
class Solution {
public int getMoneyAmount(int n) {
int dp[][] = new int[n + 2][n + 2];
for (int i = n; i > 0; i--) for (int j = i + 1; j < n + 1; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j + 1; k++) dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][k - 1], dp[k + 1][j]) + k);
}
return dp[1][n];
}
}
Python:
class Solution:
def getMoneyAmount(self, n: int) -> int:
dp = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n, 0, -1):
for j in range(i + 1, n + 1):
dp[i][j] = float('inf')
for k in range(i, j + 1):
dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k)
return dp[1][n]
