When n = 10, the answer is 16 by any of the correct solutions here. However, the example in the question clearly gives a scenario that you have to pay 21 to win the game. If you only have 16, how is it possible to guarantee a win?
I see a post said this problem is essentially "Best strategy and worst luck". However, assume there is a person coming into play, how is it possible that he knows the best strategy? If not, he is very likely to make some bad moves. If a win needs to be guaranteed, then should we consider the "worst strategy"?
So my question is, why each time we minimize the max cost?
However, the example in the question clearly gives a scenario that you have to pay 21 to win the game. If you only have 16, how is it possible to guarantee a win?
By playing smarter than in that example. It just shows how the game works, not an optimal strategy. And there is a strategy for which you only need $16 to guarantee a win. Hence, claiming you need $21 dollars to guarantee a win would be wrong.
The example in the problem description was intended to demonstrate the rules of the game. It does not reflect the optimal strategy.
The problem is to find a strategy that minimizes the cost for any possible secret number in [1..N]. If a player adheres to that strategy, it will be impossible for them to lose more than this minimum.
You can visualize the strategy as a binary tree. For N = 10:
The secret number can be any number [1..10] but if you choose your sequence of guesses by following the left or right branches according to whether your guess was high or low, then you will always guess the right number while losing no more than $16.
@StefanPochmann Thanks, I see your point here. Basically the question is asking the minimum money that you need to have to generate at least one possible way to win the game. Is it fair to say so?
@TonyLic Depends on what you mean with "generate at least one possible way to win the game" (I don't understand what you mean with that).
@magmoid When I revisited this question again, I found out your explanation is wonderful!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.