Guess Number Higher or Lower II
这个题目还是蛮有意思的
给定整数n,假定我选中的数1到n中的C，我只提示你猜的数与C的大小关系，这样你就可以缩小范围，继续猜测，但是你猜错数字，就要支付等值的美元，我为了获得更多的美元，会通过高低引导你，比如
n = 10
1,2,3,4,5,6,7,8,9,10
这时候如果你第一次选中9，我要是提示你猜小了，则你下一个就可以猜出10，因为只有一个数可以选择，那么我只能得到9美元，如果我告诉你猜高了，还有很多数字可选，这样我也可以获得更多美元。
假如你第一次选择的是7，如果告诉你猜低了，往高了猜你会猜几呢，一开始觉得猜7+10均值8，那么我可以告诉你还是猜低了，这时候你再猜8+10均值9，我还是可以告诉你猜低了，因为还有10，你要支付7+8+9，如果一个开始猜完7，直接猜测8+10均值9，这样无论我说猜低猜高了，你都可以获得答案是8或者10，只需支付7+9，16美元
这个题目可以用动态规划求解，不断就将问题分解成规模小子问题，终结条件就是问题不可分了。而且开始选择都是从中间往后开始猜，这样才能少支付美元，程序性能会提升很多
import numpy as np
class Solution(object):
def getMoneyAmount(self, n):
return self.dp(1, n)
"""
:type n: int
:rtype: int
"""
dic = {}
def dp(self, start, end):
if (start, end) in self.dic:
return self.dic[(start,end)]
if start >= end:
self.dic[(start,end)] = 0
return 0
elif (start == end - 1):
self.dic[(start,end)] = start
return start
elif (start == end -2):
self.dic[(start,end)] = start+1
return start+1
else:
temp = np.maximum
for i in range((start+end)/2, end+1,1):
temp = min(temp, i + max(self.dp(start, i-1), self.dp(i+1, end)))
self.dic[(start,end)] = temp
return temp
