力扣刷题 day46：10-16

1.最大整除子集

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。

方法一：动态规划 

#方法一:动态规划
def largestDivisibleSubset(nums):
    nums=sorted(nums) #先排序
    res=[[i] for i in nums]  #表示以i结尾的最大整除子集
    m=[nums[0]]  #结果
    for i in range(len(nums)):
        for j in range(i):
            if nums[i]%res[j][-1]==0 and len(res[j])+1>len(res[i]):
                res[i]=res[j]+[nums[i]]  #找到当前元素能整除的前面子集的最末尾元素，并且可以更新以当前元素结尾的子集
        if len(res[i])>len(m):
            m=res[i]  #更新结果
    return m

2.猜数字大小 II 

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

我从 1 到 n 之间选择一个数字。
你来猜我选了哪个数字。
如果你猜到正确的数字，就会 赢得游戏 。
如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。
给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

 

方法一：记忆化搜索 

 

#方法一：记忆化搜索
def getMoneyAmount(n):
    def dfs(i,j):
        if i+1==j:
            return i #只有两个数，猜最小的，然后就知道答案了
        if i ==j:
            return 0 #只有一个数，不用猜了
        res=float('inf')
        for k in range(i+1,j):
            res=min(res,max(dfs(i,k-1),dfs(k+1,j))+k)  #分成三个部分 i,k-1 k k+1,j
        return res
    return dfs(1,n)