Guess Number Higher or Lower II

這個題目還是蠻有意思的
給定整數(shù)n,假定我選中的數(shù)1到n中的C，我只提示你猜的數(shù)與C的大小關(guān)系，這樣你就可以縮小范圍，繼續(xù)猜測，但是你猜錯數(shù)字，就要支付等值的美元，我為了獲得更多的美元，會通過高低引導(dǎo)你，比如
n = 10
1,2,3,4,5,6,7,8,9,10
這時候如果你第一次選中9，我要是提示你猜小了，則你下一個就可以猜出10，因為只有一個數(shù)可以選擇，那么我只能得到9美元，如果我告訴你猜高了，還有很多數(shù)字可選，這樣我也可以獲得更多美元。

假如你第一次選擇的是7，如果告訴你猜低了，往高了猜你會猜幾呢，一開始覺得猜7+10均值8，那么我可以告訴你還是猜低了，這時候你再猜8+10均值9，我還是可以告訴你猜低了，因為還有10，你要支付7+8+9，如果一個開始猜完7，直接猜測8+10均值9，這樣無論我說猜低猜高了，你都可以獲得答案是8或者10，只需支付7+9，16美元
這個題目可以用動態(tài)規(guī)劃求解，不斷就將問題分解成規(guī)模小子問題，終結(jié)條件就是問題不可分了。而且開始選擇都是從中間往后開始猜，這樣才能少支付美元，程序性能會提升很多

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