0375.md

title	description	keywords
375. 猜数字大小 II	LeetCode 375. 猜数字大小 II题解，Guess Number Higher or Lower II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 375. 猜数字大小 II 猜数字大小 II Guess Number Higher or Lower II 解题思路 数学 动态规划 博弈

375. 猜数字大小 II

🟠 Medium  🔖  数学 动态规划 博弈  🔗 力扣 LeetCode

题目

We are playing the Guessing Game. The game will work as follows:

1. I pick a number between 1 and n.
2. You guess a number.
3. If you guess the right number, you win the game.
4. 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.
5. 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 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 $0. Otherwise, you pay $1.

  • If my number is higher, it must be 2. Guess 2. Your total is $1.

The worst case is that you pay $1.

Constraints:

• 1 <= n <= 200

题目大意

我们正在玩一个猜数游戏，游戏规则如下：

1. 我从 1 到 n 之间选择一个数字。
2. 你来猜我选了哪个数字。
3. 如果你猜到正确的数字，就会 赢得游戏 。
4. 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
5. 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。

给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

解题思路

用 f(i, j) 表示在范围 [i, j] 内确保胜利的最少金额，目标是计算 f(1, n)。

假设第一次猜的数字是 x 并且猜错，则需要支付金额 x，当 x 大于所选数字时，为了确保胜利还需要支付的金额是 f(1, x - 1)，当 x 小于所选数字时，为了确保胜利还需要支付的金额是 f(x + 1, n)。为了在任何情况下都能确保胜利，应考虑最坏情况，计算 f(1, n) 时应取上述两者的最大值：f(1, n) = x + max(f(1, x − 1), f(x + 1, n))。

由于 f(1, x - 1) 和 f(x + 1, n) 都是比原始问题 f(1, n) 规模更小的问题，因此可以使用动态规划的方法求解。

为了将确保胜利的金额最小化，需要遍历从 1 到 n 的所有可能的 x，使得 f(1, n) 的值最小：

f(1, n) = min{x + max⁡(f(1, x − 1), f(x + 1, n))} (⁡1 ≤ x ≤ n)

创建行数和列数都是 n + 1 的二维数组 f，其中 f[i][j] 即为状态 f(i, j)。

在根据状态转移方程计算时需要注意下标的边界问题，当 j = n 时，如果 x = j 则 x + 1 > n，此时 f[x][j] 会出现下标越界。为了避免出现下标越界，计算 f[i][j] 的方法是：首先令 f[i][j] = j + f[i][j - 1]，然后遍历 i ≤ x < j 的每个 x，更新 f[i][j] 的值。

代码

/**
 * @param {number} n
 * @return {number}
 */
var getMoneyAmount = function (n) {
	const f = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
	for (let i = n - 1; i >= 1; i--) {
		for (let j = i + 1; j <= n; j++) {
			f[i][j] = j + f[i][j - 1];
			for (let x = i; x < j; x++) {
				f[i][j] = Math.min(f[i][j], x + Math.max(f[i][x - 1], f[x + 1][j]));
			}
		}
	}
	return f[1][n];
};

相关题目

题号	标题	题解	标签	难度	力扣
294	翻转游戏 II 🔒		记忆化搜索 数学 动态规划 2+	🟠	🀄️ 🔗
374	猜数字大小	[✓]	二分查找 交互	🟢	🀄️ 🔗
464	我能赢吗		位运算 记忆化搜索 数学 3+	🟠	🀄️ 🔗
658	找到 K 个最接近的元素	[✓]	数组 双指针 二分查找 3+	🟠	🀄️ 🔗