leetcode 力扣 375. 猜数字大小 II python

目录

1. 解答

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

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

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

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

示例:

n = 10, 我选择了8.

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

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

你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

分治法，

当区间长度为 1 时（l == r），费用是 0。
当区间长度为 2 时（r - l == 1），费用是 l（较小的那个数）。
当区间长度为 3 时（r - l == 2），费用是 l + 1（中间那个数）。

区间长度更长，我们就直接分成两个区间做，取两个区间里最大的一个就成了。

但是这个切分点（代码里是 x）不好找，试了几种都不行，干脆枚举了，从 l + r // 2 开始一直到 r - 1。

这里必须使用 @functools.lru_cache(None) 装饰器，否则超时。

import functools
class Solution:
    @functools.lru_cache(None)
    def solve(self, l, r):
        if l == r: return 0
        if r - l == 1: return l
        if r - l == 2: return l + 1
        ans = sum(range(r))
        for x in range(l+r>>1, r):
            ans = min(max(self.solve(l, x-1), self.solve(x+1, r))+x, ans)
        return ans

    def getMoneyAmount(self, n: int) -> int:
        return self.solve(1, n)