Medium

题目描述

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

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

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

示例 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 = 1
输出：0
解释：只有一个可能的数字，所以你可以直接猜 1 并赢得游戏，无需支付任何费用。

示例 3：

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

提示：

  • 1 <= n <= 200

解题思路

这是一道经典的动态规划问题，核心在于理解极小化极大值的策略。

问题分析： 我们需要找到一种猜数策略，使得在最坏情况下的花费最小。这是一个对抗性的博弈问题，对手会选择让我们花费最多的数字。

思路：

  1. 使用动态规划，定义 dp[i][j] 表示在区间 [i,j] 内猜中数字所需的最小花费
  2. 对于区间 [i,j]，我们需要考虑选择哪个数字 k 作为猜测点
  3. 选择数字 k 后，有三种情况：
    • 猜中了，花费为 0
    • 目标数字在 [i,k-1]，需要额外花费 dp[i][k-1]
    • 目标数字在 [k+1,j]，需要额外花费 dp[k+1][j]
  4. 为了保证能赢，我们需要考虑最坏情况，即 k + max(dp[i][k-1], dp[k+1][j])
  5. 我们要在所有可能的 k 中选择使花费最小的那个

状态转移方程：

  • dp[i][j] = min(k + max(dp[i][k-1], dp[k+1][j])) 其中 i <= k <= j
  • 边界条件：当 i >= j 时，dp[i][j] = 0

推荐解法： 区间DP，时间复杂度O(n³)，空间复杂度O(n²)。

代码实现

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = INT_MAX;
                for (int k = i; k <= j; k++) {
                    int cost = k + max(dp[i][k-1], dp[k+1][j]);
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }
        
        return dp[1][n];
    }
};

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

public class Solution {
    public int GetMoneyAmount(int n) {
        int[,] dp = new int[n + 2, n + 2];
        
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                dp[i, j] = int.MaxValue;
                for (int k = i; k <= j; k++) {
                    int cost = k + Math.Max(dp[i, k-1], dp[k+1, j]);
                    dp[i, j] = Math.Min(dp[i, j], cost);
                }
            }
        }
        
        return dp[1, n];
    }
}

var getMoneyAmount = function(n) {
    const dp = Array(n + 2).fill().map(() => Array(n + 2).fill(0));
    
    for (let len = 2; len <= n; len++) {
        for (let i = 1; i <= n - len + 1; i++) {
            let j = i + len - 1;
            dp[i][j] = Infinity;
            for (let k = i; k <= j; k++) {
                let cost = k + Math.max(dp[i][k-1], dp[k+1][j]);
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    
    return dp[1][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)三层循环：区间长度、起始位置、猜测点
空间复杂度O(n²)二维DP数组存储所有区间的最小花费

相关题目