375.猜数字大小 II

https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/

一、dfs

比较容易想到的做法为使用「递归」进行求解。

由题目给的图，就是构造一棵树，使所有根到叶节点（不包括叶）的路径和最大值最小，只能是遍历穷举所有树。

设计递归函数为 int dfs(int l, int r) 传入参数 l 和 r 代表在范围[l,r] 内进行猜数，返回值为在[l,r] 内猜中数字至少需要多少钱。

我们可决策的部分为「选择猜哪个数x」，而不可决策的是「选择某个数 x 之后（假设没有猜中），真实值在落在哪边」。

求“确保你获胜 的最小现金数”，即「最坏情况下最好」的结果，我们应当取所有的 x 中的最小值。

TLE

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        def dfs(l, r):
            if l >= r:
                return 0
            ans = sys.maxsize
            # 遍历在[l,r]之间的每一个数x，求每种情况的最小值
            for x in range(l, r + 1):
                # （最坏情况）当选择的数为x时，至少需要cur才能猜中数字
                cur = max(dfs(l, x - 1), dfs(x + 1, r)) + x
                # （最优）在所有可以决策的数值之间取最优
                ans = min(ans, cur)
            return ans

        return dfs(1, n)

优化

加备忘录，减少重复计算，确保每个区间只计算一次

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        memo = [[0] * (n+1) for _ in range(n+1)]
        def dfs(l, r):
            if l >= r:
                return 0
            if memo[l][r]:	#备忘录有记录直接返回
                return memo[l][r]
            ans = sys.maxsize
            # 遍历在[l,r]之间的每一个数x，求每种情况的最小值
            for x in range(l, r + 1):
                # （最坏情况）当选择的数为x时，至少需要cur才能猜中数字
                cur = max(dfs(l, x - 1), dfs(x + 1, r)) + x
                # （最优）在所有可以决策的数值之间取最优
                ans = min(ans, cur)
            memo[l][r] = ans
            return ans

        return dfs(1, n)