Guessing a Number, Worst Case
A number is hidden somewhere in 1..n. You guess a value; if it is wrong you are told
whether the hidden number is higher or lower, and you pay the value you guessed. If it is
right you pay nothing more.
Print the smallest amount you can GUARANTEE to be enough, whatever the hidden number is.
n = 10 -> 16
n = 1 -> 0 no guess is needed
n = 2 -> 1 guess 1; if wrong the answer must be 2
## The objective is a minimax
The answer is not the expected cost and not the cost of the luckiest sequence. You choose the guesses, and an adversary chooses the hidden number to make you pay as much as possible.
So the value of a guess x in a range is
x + max( cost of the left part, cost of the right part )
and you pick the x minimising that. The max is the adversary and the min is you.
Writing min where the max belongs gives the luckiest-path cost, which is much smaller
and looks plausible. On n = 10 it gives a number well below 16.
## Why binary search is not the answer
Halving the range minimises the NUMBER of guesses, and here guesses have different prices. Guessing a large number costs a lot even when it splits the range well, so the optimal first guess is usually below the midpoint.
For n = 10 the answer is 16, and no binary-search sequence achieves it. That is the point
of the problem: the familiar strategy optimises the wrong quantity.
## The state
dp[lo][hi] = the guaranteed cost for the range lo..hi
dp[lo][hi] = 0 when lo >= hi
A range of one number needs no guess: if only one candidate remains, it IS the answer and nothing more is paid. Charging for it inflates every result.
n = 1 answering 0 is the test for that, and n = 2 answering 1 is the test for the other
side: guess the smaller, and if wrong the remaining range has size one and costs nothing
more.
## The recurrence
dp[lo][hi] = min over x in lo..hi of x + max( dp[lo][x-1], dp[x+1][hi] )
with out-of-range halves contributing 0.
## Fill by increasing length
dp[lo][hi] reads strictly shorter ranges, so the loop is over length, as everywhere in
this topic.
## The growth
n 1 2 3 4 5 6 7 8 10
cost 0 1 2 4 6 8 10 12 16
Those values are worth having in front of you: they are not a simple formula, they are not
n log n, and checking a solution against several of them at once catches an off-by-one
that any single value would miss.
## Cost
Time O(n^3). Space O(n^2).