脚本宝典收集整理的这篇文章主要介绍了375. 猜数字大小 II,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
我们正在玩一个猜数游戏,游戏规则如下:
我从 1 到 n 之间选择一个数字。你来猜我选了哪个数字。如果你猜到正确的数字,就会 赢得游戏 。如果你猜错了,那么我会告诉你,我选的数字比你的 更大或者更小 ,并且你需要继续猜数。每当你猜了数字 x 并且猜错了的时候,你需要支付金额为 x 的现金。如果你花光了钱,就会 输掉游戏 。给你一个特定的数字 n ,返回能够 确保你获胜 的最小现金数,不管我选择那个数字 。
dp不可能dp的,只会暴搜吃吃烂分
1 class Solution: 2 def getMoneyAmount(self, n: int) -> int: 3 self.dict = {} 4 return self.seArch(0, n) 5 6 def search(self, left, right): 7 if right <= left: 8 return 0 9 10 if self.dict.get((left, right), False): 11 return self.dict.get((left, right)) 12 13 # splIT_index = self.find_split_index(nums) 14 max_cost = float('inf') 15 16 for split_index in range(left, right + 1): 17 cost = split_index 18 cost += max(self.search(left, split_index - 1), self.search(split_index + 1, right)) 19 max_cost = min(max_cost, cost) 20 self.dict[(left, right)] = max_cost 21 22 return max_cost
以上是脚本宝典为你收集整理的375. 猜数字大小 II全部内容,希望文章能够帮你解决375. 猜数字大小 II所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。