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]新闻热点
疑难解答
