1回答

liuyubobobo

2018-04-27

已采纳

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

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

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

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

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

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

加油！

0

4

liuyubobobo

回复

站在巨人的肩膀上丶

原来官方的这个Solution是只有会员才能看的啊！我一直以为对所有人都是开放的。。。 汗。。。n=10的时候，16是一个搜索的结果，这个问题的关键就在于：我们是不能（至少我认为不能）思考一个特定的策略，然后就按照这个策略进行模拟得到答案。而是需要对于不同的n，进行一个搜索过程。具体的，当n=10的时候，不管我选什么数字，你首先猜7，如果猜对了，ok；如果我选的数字比7大，你猜9，不管我选的数字是8还是10，你的费用都是16（7+9），如果我选的数字就是9，你的费用是7；如果一开始，我选的数字比7小，你猜4，如果我的选的数字比4大，你猜5，那么如果我选的数字是6，你的费用是16（7+4+5），否则如果我选的数字是4或者5，你的费用更少；但如果我选的数字比4还要小，你猜2，如果我选的数字是1或者3，你的费用是13(7+4+2)。使用这个过程，不管我选的数字是1-n中的多少，你都可以在16的费用下，猜到我选的数字：）

2018-04-28

共4条回复