leetcode 375. Guess Number Higher or Lower II

Question

波波老师我怎么不是很理解这道题的意思呀，题目中给的那个例子，好像都不是正确的一个解啊，对于这种minmax类型的题目求解的大体思路应该是什么样的呢？

Answer 1

liuyubobobo 2018-04-27 15:59:44

题目中给的例子，只是一次游戏过程而已。但是，让你求的是，按照这种游戏过程，你手里有多少钱，保证可以赢。

换句话说，假定你是猜数字的人，我是选数字的人。你手里至少有多少钱，对于给定的n，不管我选择什么数字，你手里的钱都足以支付罚金，直到你猜到正确的答案。

这个问题整体是个动态规划的问题。不过对动态规划不是特别熟悉的同学，可能不能一眼看出来。其实对于算法比赛中的所有的问题，我的建议都是：如果你没有直接的思路，就去暴力求解，也就是搜索求解。而不是去找相应的算法。在暴力搜索求解的过程中，你可能就能观察到问题的一些性质，比如是否可以剪枝，或者是否有重叠子问题可以转成动态规划求解，或者是否蕴含着贪心选择性质，等等等等。

在一些算法竞赛中，使用暴力求解解决小数据量还能得分；在笔试面试中，对于一个问题，能暴力搜索得到解比没有解也要强：）

这个问题使用动态规划的重叠子问题，如果能够写出暴力搜索的解法，整体还是很明显的。不存在隐藏的状态转换。可能因为这个原因，标成是中等难度。这个问题在官方网站有官方的解题指南，写的还是挺详细的。只可惜从暴力求解到dp求解，少了中间的记忆化搜索的过度。建议看懂暴力求解的思路和dp算法状态定义的方式后，自己写一个记忆花搜索的解法，相信会理解更深刻：）

传送门：https://leetcode.com/problems/guess-number-higher-or-lower-ii/solution/

加油！

• 提问者 站在巨人的肩膀上丶 #1

  非常感谢！

• 提问者 站在巨人的肩膀上丶 #2

  波波老师我刚才试了一个AC的代码，当n为10的时候他的解为16，波波老师能够解释一下这个结果是怎么得到的吗？(还有这个solution我们不是leetcode会员的现在都看不到了。。。)

• 提问者 站在巨人的肩膀上丶 #3

  按我的理解，当n为10的时候不管是选择什么数字，猜数字的人第一个肯定是要猜5的因为这样能排除较多的数字，也就是说这也相当于一个二分查找的过程，但是按这样思路的话求到的值会比16更大。

点开查看后面1条评论