题目链接：375. 猜数字大小 II
动态规划。
最优子结构+公共子问题。
这个问题其实是求，这 n 个数字组成的排序二叉树，从根结点到叶子结点(不计算叶子结点)之间的非叶子结点值的最大和，最小是多少。
递归的思路：拿到这 len(arr)=n 个数字，从中取第 i 个数字作为根结点，那么 arr[:i] 组成其左子树，arr[i+1:] 组成其右子树， 根结点到叶子结点(不计算叶子结点)之间的非叶子结点值的最大和是 max(func(arr[:i]), func(arr[i+1:]))+arr[i]。
遍历所有 i，取最小值。
class Solution:
def get_amount(self, l: int, r: int):
if r - l <= 0:
val = 0
elif r - l == 1:
val = l
elif r - l == 2:
val = l + 1
else:
val = min(max(self.get_amount(l, m - 1), self.get_amount(m + 1, r)) + m for m in range(l + 1, r))
return val
def getMoneyAmount(self, n: int) -> int:
return self.get_amount(1, n)
递归解法能得到正确的结果，但时间复杂度太高。观察递归结构，具有公共子问题和最优子结构的性质。那么考虑将递归解法转为动态规划。
class Solution:
def __init__(self):
self.cache = dict()
def get_amount(self, l: int, r: int):
if (l, r) in self.cache:
return self.cache.get((l, r))
if r - l <= 0:
val = 0
elif r - l == 1:
val = l
elif r - l == 2:
val = l + 1
else:
val = min(max(self.get_amount(l, m - 1), self.get_amount(m + 1, r)) + m for m in range(l + 1, r))
self.cache[(l, r)] = val
return val
def getMoneyAmount(self, n: int) -> int:
return self.get_amount(1, n)