猜数字大小 II

难度:

标签:

题目描述

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

我从 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

代码结果

运行时间: 35 ms, 内存: 16.1 MB

// Solution using Java Streams
// The solution remains the same in terms of logic, but we'll leverage Java Streams for handling collections.
// The key idea is still dynamic programming to minimize the maximum loss.
 
import java.util.stream.IntStream;
 
public class GuessNumberStream {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        IntStream.rangeClosed(2, n).forEach(len ->
            IntStream.rangeClosed(1, n - len + 1).forEach(start ->
                dp[start][start + len - 1] = IntStream.range(start + (len - 1) / 2, start + len - 1)
                    .map(piv -> piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]))
                    .min().orElse(Integer.MAX_VALUE)
            )
        );
        return dp[1][n];
    }
}

解释

方法:

这个题解使用了动态规划的策略来解决问题。定义一个二维数组 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)

代码细节讲解

🦆

题解中用到了二维数组dp，每个元素dp[i][j]代表什么意义？

▷

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

🦆

为什么在初始化dp数组时，dp[i][j]被初始化为i+dp[i+1][j]？这种初始化方式有什么特别的考虑吗？

▷

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

🦆

题解中提到，对于每一个k点，计算的是k + max(dp[i][k-1], dp[k+1][j])。请问为什么要选择两侧范围中的最大代价而不是最小代价？

▷

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

相关问题

翻转游戏 II