跳转至

LeetCode: 375. 猜数字大小 II

1、题目描述

我们正在玩一个猜数游戏,游戏规则如下:

我从 1n 之间选择一个数字,你来猜我选了哪个数字。

每次你猜错了,我都会告诉你,我选的数字比你的大了或者小了。

然而,当你猜了数字 x 并且猜错了的时候,你需要支付金额为 x 的现金。直到你猜到我选的数字,你才算赢得了这个游戏。

示例:

n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5,我会告诉你,我的数字更大一些,然后你需要支付5块。
第二轮: 你猜是7,我告诉你,我的数字更大一些,你支付7块。
第三轮: 你猜是9,我告诉你,我的数字更小一些,你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。

给定一个 **n ≥ 1,**计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

致谢:

特别感谢 @agave@StefanPochmann 添加了这道题目,并且提供了所有测试用例。

2、解题思路

​ 用动态规划来解决

分析一下思路,我们设置一个区间,在这个区间里面,才一个数,假设区间边界分别是,i,j

  • 如果区间中只有一个数,i=j,那么花费肯定是0,一次就猜中了

  • 如果i+1=j,那么如何保证能赢呢?每次都选小的那个数,如果挑选的正好是大的那个数,花费就是i,也就是说,只要有i,那么,不管挑选的是i还是j,肯定能赢

  • 如果i+2=j,也就是我们有三个数可以选择的时候,如何保证一定能赢呢?

首先,我们有i+1块钱,然后在前面区间和后面区间中,找到花钱最多的,加上i+1,这时候,就找到了

因为你会告诉我是大了还是小了,因此,3个数猜,肯定是中间的,i+1,因此,

  • 以此类推,假如想要找从1到10的花费,那么,将区间分开,

假设我们第一次挑选的数字是5,因为你会告诉我猜的大了,还是猜的小了,因此,花费就是5加上前面区间和后面区间中较大的那个,这样才能保证能赢

假如想要的到1-10,

1+dp[2][10]
2+ max(dp[1][1], dp[3][10])
3+ max(dp[1][2], dp[4][10])
4+ max(dp[1][3], dp[5][10])
5+ max(dp[1][4], dp[6][10])
6+ max(dp[1][5], dp[7][10])
7+ max(dp[1][6], dp[8][10])
8+ max(dp[1][7], dp[9][10])
9+ max(dp[1][8], dp[10][10])
10+ dp[1][9]

​ 当我们求解1-9的时候,1-9之间的组合已经有了,但是前面的数到10的组合还没有,因此,需要从后面向前运算

​ 也就是先将dp[9][10]算出来,然后是根据这个,就能计算dp[8][10]

​ 一次类推,最后,我们就得到了dp[1][10]

class Solution:
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0] * (n + 1) for _ in range(n + 1)]

        for j in range(2, n + 1):
            for i in range(j - 1, 0, -1):
                temp = 0x7fffffff
                for k in range(i + 1, j):
                    current = k + max(dp[i][k - 1], dp[k + 1][j])
                    temp = min(temp, current)

                if i + 1 == j:
                    dp[i][j] = i
                else:
                    dp[i][j] = temp
        return dp[1][n]