A# Question
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.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
猜數字游戲，A在1-n中選擇一個數字，當B猜中A選擇的數字，B就贏得比賽。每當B猜錯，A會告訴B是否太大還是太小，同時B要給A對應猜的數字的錢。現在給出n，請你找出你保證贏得比賽所需花費的最少的錢
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.
這里的例子給出的21只是一種猜測情況所需的花費，而不是題目的答案
根據上面的思路，我們定義dp[i][j]：在[i, j]范圍中保證贏得游戲所需花費最少的錢。因為是最壞的情況，所以在策略最優的情況下，B始終不會猜中數字，那么當B猜數字x的情況下，子問題將會出現兩種情況“猜的數字過小”，“猜的數字過大”，我們只需要比較出花費較多的情況即可，所以B猜數字x的最大花費為：B_Choose_X = x + max(dp[i][x - 1]， dp[x + 1][j])，在得到A選擇任意x，B所需的最大花費時，dp[i][j] = min{B_Choose_1, B_Choose_2, …, B_Choose_N}
class Solution(object): def getMoneyAmount(self, n): """ :type n: int :rtype: int """ self.dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)] return self.solve(1, n) def solve(self, s, e): # 保存dp中間變量，減少重復計算 if self.dp[s][e] != 0: return self.dp[s][e] # 如果只有一個數字可以選擇，那么B肯定能猜中，不需要花費錢 if s >= e: return 0 min_cost = float('inf') # 計算A選擇任一數字，B所需的最多的錢 for x in range(s, e): max_cost = x + max(self.solve(s, x - 1), self.solve(x + 1, e)) if min_cost > max_cost: min_cost = max_cost # 取所需最少的錢的情況 self.dp[s][e] = min_cost return self.dp[s][e]新聞熱點
疑難解答
