猜数字大小 II

难度: Medium

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

我从 1 到 n 之间选择一个数字。
你来猜我选了哪个数字。
如果你猜到正确的数字，就会 赢得游戏 。
如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
每当你猜了数字 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

Submission

运行时间: 35 ms

内存: 16.1 MB

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        def min(x,y):
            if x>=y:return y
            return x
        def max(x,y):
            return x if x>y else y
        dp=[[0]*(1+n) for _ in range(1+n)]
        for j in range(1,n+1):
            for i in range(j-1,-1,-1):
                dp[i][j]=i+dp[i+1][j]
                for k in range(i+1,j):
                    dp[i][j]=min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j]))
        return dp[0][-1]
        @cache
        def dfs(left,right):
            if right-left==1:
                return left
            elif right-left==2:
                return left+1
            elif right-left==3:return left+left+2
            elif left>=right:return 0
            ans=inf
            for i in range(left+1,right):
                ans=min(ans,i+max(dfs(left,i-1),dfs(i+1,right)))
            return ans
        return dfs(1,n)

Explain

这个题解使用了动态规划的策略来解决问题。定义一个二维数组 dp，其中 dp[i][j] 表示在范围 i 到 j 内确保胜利的最小支付金额。我们从较小的范围开始计算，并逐步扩展到整个范围。对于每一个范围 [i, j]，我们考虑所有可能的猜测点 k，计算在猜测点 k 失败后，左侧范围 [i, k-1] 和右侧范围 [k+1, j] 中较大的代价，并加上当前的猜测代价 k，从而更新 dp[i][j]。通过这种方式，我们可以填满整个 dp 表，dp[0][n] 就是从 1 到 n 确保胜利所需的最小金额。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        # 自定义小的min函数
        def min(x,y):
            return y if x >= y else x
        # 自定义大的max函数
        def max(x,y):
            return x if x > y else y
        # 初始化dp数组
        dp = [[0] * (1 + n) for _ in range(1 + n)]
        # 外层循环，逐步扩大范围
        for j in range(1, n + 1):
            # 内层循环，从后向前计算
            for i in range(j - 1, -1, -1):
                # 初始化dp[i][j]为i+dp[i+1][j]，即考虑最小的i作为猜测点
                dp[i][j] = i + dp[i + 1][j]
                # 中间层循环，考虑所有可能的猜测点
                for k in range(i + 1, j):
                    # 更新dp[i][j]为从k点猜错后两侧的最大代价加上当前猜测代价k
                    dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j]))
        # 返回整个范围的最小代价
        return dp[0][-1]

Explore

在这个问题中，每个元素dp[i][j]表示的是在数字范围i到j之间，为了确保无论对方选择哪个数字你都能赢得游戏，你需要支付的最小金额。

这种初始化方式考虑的是最小可能的猜测点情况，即当你首先猜测最小的边界数字i时的情况。如果猜测错误（实际数字大于i），则你需要支付i元，并且面对的新范围是[i+1, j]。因此，总的最小成本就是猜测成本i加上新范围[i+1, j]的最小成本。这是一种保守的初始化，为后续的计算提供一个基准值。

选择两侧范围中的最大代价是因为我们需要考虑最坏情况，即对手选择了使你支付最多的数字。如果你猜测数字k并且猜错了，你需要继续在两个新的范围[i, k-1]或[k+1, j]中猜测。这里的最大代价确保了无论对手如何选择，你都有足够的资金来继续游戏，从而确保能赢得游戏。选择最小代价可能导致在某些不利情况下资金不足，无法继续游戏。