LeetCode 375 猜数字大小II

题目描述

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

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

题目解读

• 可决策部分：选择猜哪个数 x
• 不可决策部分：选择某个数 x 之后，如果没有猜中，真实值会落在哪边
  • 求最坏情况下的最好结果，取所有 x 中的最小值

解题思路

动态规划 - 穷举所有可能的结果

这里使用一个二维数组dp[n+1][n+1]。

dp[i][j]含义：从i到j的数字依次作为分割点（我们猜的数），保证赢得游戏前提下的最小值。

• dp[1][1]

dp[1][1]是指只有一个数字1，我们以1作为分割点(猜的数)，赢得游戏所用钱的最小值。dp[1][1]=0

• dp[1][2]

dp[1][2]是指只有两个数字1，2：

以1作为分割点：
答案是1，花费0元
答案是2，花费1元
必定赢得游戏，最多花费1元

以2作为分割点：
答案是1，花费2元
答案是2，花费0元
必定赢得游戏，最多花费2元

综上，在这个区间内，先猜1的话，只要花费1元就可以保证赢得游戏。→dp[1][2] = 1

• dp[2][3]

dp[2][3]是指只有两个数字2，3：

以2作为分割点：  
答案是2，花费0元
答案是3，花费2元
必定赢得游戏，最多花费2元

以3作为分割点：
答案是2，花费3元
答案是3，花费0元
必定赢得游戏，最多花费3元

dp[2][3] = 2

• dp[1][3]

dp[1][3]是指只有三个数字1，2，3：

以1作为分割点：
答案是1，花费0元
答案是2或者3，这个时候会进入另一个区间[2,3]，花费1+dp[2][3]元
必定赢得游戏，最多花费max(0,1+dp[2][3])元

以2作为分割点：
答案是1，花费2+dp[1][1]=2+0=2元
答案是2，花费0元
答案是3，花费2+dp[3][3]=2+0=2元
必定赢得游戏，最多花费max(0,2+dp[1][1],2+dp[3][3])元

以3作为分割点：
答案是1或者2,花费3+dp[1][2]元
答案是3，花费0元
必定赢得游戏，最多花费max(0,3+dp[1][2])元

dp[1][3] = min(max(0,1+dp[2][3]), max(0, 2+dp[1][1], 2+dp[3][3]), max(0, 3+dp[1][2]))

综上，问题的答案就是dp[1][n]

• 状态转移方程
  • 对于每一个分割点，取它左右两边区间的最大值加上分割点本身作为取此分割点的dp[i][j]值
  • 对于每一个区间，我们取所有分割点的dp[i][j]的最小值作为dp[i][j]的真正的值
  • 特别地，对于以i作为分割点的dp[i][j]，只取i右边的区间；对于以j作为分割点的dp[i][j]，只取j左边的区间

i i+1 i+2 ... ... j-2 j-1 j
以i+1为分割点对应的：dp1=max(dp[i][i],dp[i+2][j])+i+1
以j-1为分割点对应的: dp2=max(dp[i][j-2],dp[j][j])+j-1
特别地,以i为分割点：dp0=i+dp[i+1][j];以j为分割点: dp3=j+dp[i][j-1]
dp[i][j]=min(dp0,dp1,dp2,dp3)

• 数组的填充

(1)初始化：                (2)上三角矩阵
|0 0 0 0|                |0 0 0 0|
|0 0 0 0|                |  0 0 0|
|0 0 0 0|                |    0 0|
|0 0 0 0|                |      0|

(3)填充
|0 0 0 0|                |0 0 0 0|
|  0 0 0|                |  0 2 x|
|    0 3|                |    0 3|
|      0|                |      0|

代码

class Solution{
    public int getMoneyAmount(int n){
        int dp[][] = new int[n+1][n+1];
        for(int i=n-1; i>=1; i--){
            for(int j=i+1; j<=n; j++){            // 从dp[n-1][n]开始填充
                int min = Integer.MAX_VALUE;
                for(int p=i; p<j; p++){            // 比较不同分割点的 
                    int cost = p + Math.max(dp[p+1][j], dp[i][p-1]);
                    min = Math.min(min, cost);
                }
                dp[i][j] = min;
            }
        }
        return dp[1][n];
    }
}