e 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. 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.
Clarification of the problem: https://discuss.leetcode.com/topic/68252/clarification-on-the-problem-description-problem-description-need-to-be-updated
It is actually confusing that the example shown in the problem description is not the best stragety to guess the final target number, and the problem itself is asking for the lowest cost achieved by best guessing strategy. We can also understand in this way, your guessing strategy is the best, but your luck is the worst(every time your guess is wrong until there's no possibility to make mistake)
The example description should be updated.
---POSSIBLY, it can also add some example about the BEST Strategy---
The example description should be:
first introducebest strategyto guess:
-
for one number, like 1, best strategy is 0$ -
for two number, like 3,4, best strategy is 3$, which can be understood in this way: you have two way to guess: a) start by guess 4 is the target, (the worst case is) if wrong, you get charged $4, then immediately you know 3 is the target number, get get charged $0 by guessing that, and finally you get charged $4. b) similarly, if you start by 3, (the worst case is) if wrong, you get charged $3, then you immediately know that 4 is the target number, and get charged $0 for guessing this, and finally you get charged $3. In summary:
range ---------> best strategy cost
3, 4 ---------> $3
5, 6 ---------> $5
... -
for three number, the best strategy is guess the middle number first, and (worst case is) if wrong, you get charged that middle number money, and then you immediately know what target number is by using "lower" or "higher" response, so in summary:
range ---------> best strategy cost
3, 4, 5 ---------> $4
7, 8, 9 ---------> $8
... -
for more numbers, it can simply be reduced them into smaller ranges, and here is why DP solution make more sense in solving this.
suppose the range is [start, end]
the strategy here is to iterate through all number possible and select it as the starting point, say for any k between start and end, the worst cost for this is: k+DP( start, k-1 ) + DP(k+1, end ), and the goal is minimize the cost, so you need the minimum one among all those k between start and end
Another analysis:
The best strategy to play the game is to minimize the maximum loss you could possibly face.
Definition of dp[i][j]: minimum number of money to guarantee win for subproblem [i, j].
Target: dp[1][n]
Corner case: dp[i][i] = 0 (because the only element must be correct)
Equation: we can choose k (i<=k<=j) as our guess, and pay price k. After our guess, the problem is divided into two subproblems. Notice we do not need to pay the money for both subproblems. We only need to pay the worst case (because the system will tell us which side we should go) to guarantee win. So dp[i][j] = min (i<=k<=j) { k + max(dp[i][k-1], dp[k+1][j]) }
public class Solution {
public int getMoneyAmount(int n) {
if (n == 1) return 0;
int[][] dp = new int[n+1][n+1];
for (int len=1; len<=n-1; len++) {
for (int i=1; i+len<=n; i++) {
int j = i + len;
dp[i][j] = Integer.MAX_VALUE;
for (int k=i; k<=j; k++) {
dp[i][j] = Math.min(dp[i][j],
k+Math.max(k==i? 0 : dp[i][k-1],
k==j? 0 : dp[k+1][j]));
}
}
}
return dp[1][n];
}
}