LeetCode375 猜数字大小 II

问题描述

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

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

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

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

示例:

n = 10, 我选择了8.

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

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

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

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

致谢:

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

解题思路

解答本题时，第一思路是采用快速查找算法，但是步长少并意味着支付的金额最少。那如何解决本题了？当没有思路的时候，最笨的方法就是最好的方法，列举一些数字，看看其中有没有什么规律：

当n = 1时，显然cost = 0
当n = 2时，即[1, 2]，显然cost=1
当n = 3时，即[1, 2, 3]，只需要猜中间数字2就能知道结果，因为比2大的只有一个，比2小的也只有一个，所以cost=2
当n = 4时，即[1, 2, 3, 4] 。四个数字显然不能一眼看出最少cost，那就一个一个来计算吧：
- 如果先猜1，如果猜中，则cost=1，否则数字在[2-4]之间，这时需花费cost = 1 + Cost(2, 4) = 1 + 3 = 4。这时，应该取cost=4，为什么了，因为如果你要赢得比赛，就必须至少要带￥4，所以取大
- 如果先猜2，则cost = 2 + Cost(3,4) = 2 + 3 = 5
- 如果先猜3，则cost = 3 + Cost(1,2) = 3 + 1 = 4
- 如果先猜4，则cost = 4 + Cost(1,3) = 4 + 2 = 6
- ==综上所列==，当有4个数字时，至少要带￥4（为啥？因为按照上面的方案，至少要带够￥4元才有可能赢得这个游戏呀！）。至此已经可以看出，这是一道求局部最大值，全局最小值的问题，
当n = 5时，即[1, 2, 3, 4, 5]，同样可以挨个计算每个数字，最终得到最小cost

综上所述，当给定数字n时，可以从1开始，计算全部至少花费情况，最后取最小花费，伪代码如下：

# 计算[i, j]区间最小花费
def min_cost(i, j):
    if j <= i:
        return 0
    if j - i == 1:
        return i
    if j - i == 2:
        return i + 1
    
    # 初始最大整数
    global_min = INT_MAX
    for k in range(i, j+1):
        # k + max(左边最小花费，右边最小花费)
		local_max = k + max(min_cost(i, k-1), min_cost(k+1, j))
        global_min = min(local_max, global_min)
    return global_min

# 给定n
min_cost(1, n)

至此，本题可以采用递归的方法解决，但是算法复杂度较高，不能通过测试。通过观察发现，在递归计算过程中，有很多区间会被重复计算。一种优化策略是保存计算结果，相同计算时直接从缓存中读取。

另外一种解题方法是采用动态规划实现。比如当n=5时，

初始化一个n+1维dp数组
令i in range(2, 6)，j in range(i-1, 0, -1)，计算区间[j, i]的最小花费
- 当i = 2时
  - 当j = 1
    - 当k = 1，cost = 1
    - dp[1][2]=1
- 当i = 3时
  - 当j = 2
    - 当k = 2，cost = 2
    - dp[2][3]=2
  - 当j = 1
    - 当k = 1，cost = 1 + dp[2][3] =3
    - 当k = 2，cost = 2 + max(dp[1][1], dp[3][3]) = 2
    - dp[1][3] = 2
- 当i = 4时
  - 当j = 3
    - 当k = 3， cost = 3
    - dp[3][4] = 3
  - 当j = 2
    - 当k = 2，cost = 2 + dp[3][4] = 5
    - 当k = 3，cost = 3 + max(dp[2][2], dp[4][4]) = 3
    - dp[2][4] = 3
  - 当j = 1
    - 当k = 1， cost = 1 + dp[2][4] = 4
    - 当k = 2，cost = 2 + max(dp[1][1], dp[3][4]) = 5
    - 当k = 3，cost = 3 + max(dp[1][2], dp[4][4]) = 4
    - dp[1][4] = 4
- 当i = 5时
  - 当j = 4
    - 当k = 4， dp[4][5]=4
  - 当j = 3
    - 当k = [3, 4]，dp[3][5] = 4
  - 当j = 2
    - 当k = [2, 3, 4]，dp[2][5] = 6
  - 当j = 1
    - 当k = [1, 2, 3, 4]，dp[1][5] = 4
dp[1][5]即为最小花费金额

代码

import sys

class Solution:
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        dp = [[0] * (n+1) for _ in range(n+1)]
        
        for i in range(2, n+1):
            for j in range(i-1, 0, -1):
                global_min = sys.maxsize
                for k in range(j, i):
                    local_max = k + max(dp[j][k-1], dp[k+1][i])
                    global_min = min(local_max, global_min)
                dp[j][i] = global_min
        return dp[1][n]