题目地址: https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/
题目描述：
Weare playing the Guess Game. The game is as follows:
Ipick 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这里面的某个数字最少需要的花费。
解题方法
这个题说实话，我还真是不会，以下是细语呢喃open in new window的讲解，非常详细。建议大家看原博。
这题要求我们在猜测数字y未知的情况下（1~n任意一个数），要我们在最坏情况下我们支付最少的钱。也就是说要考虑所有y的情况。
我们假定选择了一个错误的数x，（1<=x<=n && x!=y ）那么就知道接下来应该从[1,x-1 ] 或者[x+1,n]中进行查找。 假如我们已经解决了[1,x-1] 和 [x+1,n]计算问题，我们将其表示为solve(L,x-1) 和solve(x+1,n)，那么我们应该选择max(solve(L,x-1),solve(x+1,n)) 这样就是求最坏情况下的损失。总的损失就是 f(x) = x + max(solve(L,x-1),solve(x+1,n))
那么将x从1~n进行遍历，取使得 f(x) 达到最小，来确定最坏情况下最小的损失，也就是我们初始应该选择哪个数。
上面的说法其实是一个自顶向下的过程（Top-down），可以用递归来解决。很容易得到如下的代码（这里用了记忆化搜索）：
class Solution(object):
def getMoneyAmount(self, n):
"""
:type n: int
:rtype: int
"""
dp = [[0] * (n + 1) for _ in range(n + 1)]
return self.solve(dp, 1, n)
def solve(self, dp, L, R):
if L >= R: return 0
if dp[L][R]: return dp[L][R]
dp[L][R] = min(i + max(self.solve(dp, L, i - 1), self.solve(dp, i + 1, R)) for i in range(L, R + 1))
return dp[L][R]
1 2 3 4 5 6 7 8 9 10 11 12 13 14
把递归改为迭代，方法如下：
class Solution(object):
def getMoneyAmount(self, n):
"""
:type n: int
:rtype: int
"""
dp = [[0] * (n + 1) for _ in range(n + 1)]
for l in range(n - 1, 0, -1):
for r in range(l + 1, n + 1):
dp[l][r] = min(i + max(dp[l][i - 1], dp[i + 1][r]) for i in range(l, r))
return dp[1][n]
1 2 3 4 5 6 7 8 9 10 11
参考资料：
https://www.hrwhisper.me/leetcode-guess-number-higher-lower-ii/
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发