375. Guess Number Higher or Lower II Description
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example: n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
问题描述我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例: n = 10, 我选择了8. 第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。 第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。 第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。 游戏结束。8 就是我选的数字。 你最终要支付 5 + 7 + 9 = 21 块钱。给定一个 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
问题分析 刚开始看到这个题，感觉是个数学问题，可以直接计算得出。写了很久都不AC，于是又老实写算法了。从算法角度看，这个题就是很直白的暴力破解，中间用到了DP来减小运算复杂度，还包含了取最大值和最小值运算，所以不太好分类，但是思想还是能理明白。最重要的一步DP就是i+max( [1,...,i-1] , [i+1,...,n] )。这里的[1,...,i-1]表示猜对这个短序列最少花的钱。
下面举例说明。
当序列很短的时候，一眼就能看出来最少花多少钱。比如长度为2的短序列:
1 2显然猜1可以花钱最少，猜对不花钱，错了花1块，所以最多需要1块钱。
长度为3的短序列同理。比如:
显然猜3可以花最少的钱，猜对不花钱，错了花3块，然后下一次一定可以猜对。所以最多需要3块钱。
对于这种短序列，我们很快可以得到答案，直接每个数试一试就能知道结果。具体这样试，
如果先猜2，错了再猜3(知道3比4花钱少)，那么5块钱可以保证一定猜对。
如果先猜3，不管对错，肯定能得到正确答案，那么只需3块钱。
如果先猜4，错了再猜2(知道2比3花钱少)，那么需要6块钱。
综上，选最好的猜法，最少只要3块钱即可。
这其实是我们内心的真实逻辑，写成代码就简单了，如果序列是[ i , i+1 ]和[ i-1 , i , i+1 ]这样的，直接猜i就好了。
对于中长序列，比如1到4的序列怎么处理呢，其实逻辑一样:
1 2 3 4上面[ 2 , 3 , 4 ]的例子里，猜2不对，我们知道该猜3而不是4。但对于这种长一点的序列，第一次没猜对，我们也不容易看出第二次猜哪个数比较好。
如果没有策略，纯暴力搜索把所有猜法都试一遍，复杂度是指数级的。于是我们可以在暴力搜索的基础上将任务分解成一个个小任务，即用DP的思路，创建一个二维表格，记住小任务的解，最终得到大任务的解。
比如前面[ 2 , 3 , 4 ]的例子里思路也是一样的。猜2不对，我们知道猜3而不是4，就是因为我们心里默认知道[ 3 , 4 ]这个小任务只需要猜3就够了，即[ 3 , 4 ]这个小任务只需要3块钱而不是4块钱。
这里也是同理：
先猜1
1 2 3 4那么剩下的[ 2 , 3 , 4 ]猜什么呢。上述已经知道这个序列猜3花费最少。那么最终花费是1+3=4
先猜2
1 2 3 4要是大了，左边剩一个数肯定是对的，那么花费是0。要是小了，右边的序列[ 3 , 4 ]花费3足矣。那么最少需要花的钱就是2+max(左边0,右边3)=5。
这里有个取最大的操作，原因是为了把所有情况都考虑进去，这样无论是哪一种情况，钱都是够的。
先猜3
1 2 3 4要是大了，左边的序列[ 1 , 2 ]花费1足矣。要是小了，右边只剩一个数，花费0。那么这种情况下最少需要3+max(左边1,右边0)=4
先猜4
1 2 3 4剩下的[ 1 , 2 , 3 ]花费2，最终花费4+2=6。
那么最终至少要花的钱就是min(先猜1，先猜2，先猜3，先猜4)=min(4,5,4,6)=4 。
这里有个取最小值的操作，就是在所有暴力破解的方法中，找花钱最少的那种方法，这样就能用最少的钱猜到正确数字。
另外可以看出，我们每次都把任务分解成左右两个小任务，只要知道了小任务的最优值，就能求得大任务的最优值了。