设计递归函数为 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)
