0375. 猜数字大小 II

• 标签：数学、动态规划、博弈
• 难度：中等

题目链接

• 0375. 猜数字大小 II - 力扣

题目大意

描述：现在两个人来玩一个猜数游戏，游戏规则如下：

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

现在给定一个特定数字 $n$。

要求：返回能够确保我们获胜的最小现金数（不管对方选择哪个数字）。

说明：

• $1 \le n \le 200$。

示例：

• 示例 1：

输入：n = 10
输出：16
解释：制胜策略如下：
- 数字范围是 [1,10]。你先猜测数字为 7 。
  - 如果这是我选中的数字，你的总费用为 $0。否则，你需要支付 $7。
  - 如果我的数字更大，则下一步需要猜测的数字范围是 [8, 10] 。你可以猜测数字为 9。
    - 如果这是我选中的数字，你的总费用为 $7。否则，你需要支付 $9。
    - 如果我的数字更大，那么这个数字一定是 10。你猜测数字为 10 并赢得游戏，总费用为 $7 + $9 = $16。
    - 如果我的数字更小，那么这个数字一定是 8。你猜测数字为 8 并赢得游戏，总费用为 $7 + $9 = $16。
  - 如果我的数字更小，则下一步需要猜测的数字范围是 [1, 6]。你可以猜测数字为 3。
    - 如果这是我选中的数字，你的总费用为 $7。否则，你需要支付 $3。
    - 如果我的数字更大，则下一步需要猜测的数字范围是 [4, 6]。你可以猜测数字为 5。
      - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $5。
      - 如果我的数字更大，那么这个数字一定是 6。你猜测数字为 6 并赢得游戏，总费用为 $7 + $3 + $5 = $15。
      - 如果我的数字更小，那么这个数字一定是 4。你猜测数字为 4 并赢得游戏，总费用为 $7 + $3 + $5 = $15。
    - 如果我的数字更小，则下一步需要猜测的数字范围是 [1, 2]。你可以猜测数字为 1。
      - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10。否则，你需要支付 $1。
      - 如果我的数字更大，那么这个数字一定是 2。你猜测数字为 2 并赢得游戏，总费用为 $7 + $3 + $1 = $11。
在最糟糕的情况下，你需要支付 $16。因此，你只需要 $16 就可以确保自己赢得游戏。

• 示例 2：

输入：n = 2
输出：1
解释：有两个可能的数字 1 和 2 。
- 你可以先猜 1 。
  - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $1 。
  - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $1 。
最糟糕的情况下，你需要支付 $1。

解题思路

思路 1：动态规划

直觉上这道题应该通过二分查找来求解，但实际上并不能通过二分查找来求解。

因为我们可以通过二分查找方法，能够找到猜中的最小次数，但这个猜中的最小次数所对应的支付金额，并不是最小现金数。

也就是说，通过二分查找的策略，并不能找到确保我们获胜的最小现金数。所以我们需要转换思路。

我们可以用递归的方式来思考。

对于 $1 \sim n$ 中每一个数 $x$：

1. 如果 $x$ 恰好是正确数字，则获胜，付出的现金数为 $0$。
2. 如果 $x$ 不是正确数字，则付出现金数为 $x$，同时我们得知，正确数字比 $x$ 更大还是更小。
   1. 如果正确数字比 $x$ 更小，我们只需要求出 $1 \sim x - 1$ 中能够获胜的最小现金数，再加上 $x$ 就是确保我们获胜的最小现金数。
   2. 如果正确数字比 $x$ 更大，我们只需要求出 $x + 1 \sim n$ 中能够获胜的最小现金数，再加上 $x$ 就是确保我们获胜的最小现金数。
   3. 因为正确数字可能比 $x$ 更小，也可能比 $x$ 更大。在考虑最坏情况下也能获胜，我们需要准备的最小现金应该为两种情况下的最小代价的最大值，再加上 $x$ 本身。

我们可以通过枚举 $x$，并求出所有情况下的最小值，即为确保我们获胜的最小现金数。

我们可以定义一个方法 $f(1)(n)$ 来表示 $1 \sim n$ 中能够获胜的最小现金数，则可以得到递推公式：$f(1)(n) = min_{x = 1}^{x = n} \lbrace max \lbrace f(1)(x - 1), f(x + 1)(n) \rbrace + x \rbrace)$。

将递推公式应用到 $i \sim j$ 中，可得：$f(i)(j) = min_{x = i}^{x = j} \lbrace max \lbrace f(i)(x - 1), f(x + 1)(j) \rbrace + x \rbrace)$

接下来我们就可以通过动态规划的方式解决这道题了。

1. 划分阶段

按照区间长度进行阶段划分。

2. 定义状态

定义状态 $dp[i][j]$ 表示为：数字 $i \sim j$ 中能够确保我们获胜的最小现金数。

3. 状态转移方程

$dp[i][j] = min_{x = i}^{x = j} \lbrace max \lbrace dp[i][x - 1], dp[x + 1][j] \rbrace + x \rbrace)$

4. 初始条件

• 默认数字 $i \sim j$ 中能够确保我们获胜的最小现金数为无穷大。
• 当区间长度为 $1$ 时，区间中只有 $1$ 个数，肯定为正确数字，则付出最小现金数为 $0$，即 $dp[i][i] = 0$。

5. 最终结果

根据我们之前定义的状态，$dp[i][j]$ 表示为：数字 $i \sim j$ 中能够确保我们获胜的最小现金数。所以最终结果为 $dp[1][n]$。

思路 1：代码

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
        for l in range(2, n + 1):
            for i in range(1, n + 1):
                j = i + l - 1
                if j > n:
                    break
                dp[i][j] = float('inf')
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], max(dp[i][k - 1] + k, dp[k + 1][j] + k))

        return dp[1][n]

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 为给定整数。
• 空间复杂度：$O(n^2)$。