I met a difficult problem again relate to dynamic programming (DP), the Guess Number problem.

Let’s first have a look the problem.


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.

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.

I got confused about “find out how much money you need to have to guarantee a win.” A hint says “minimize the maximum loss you could possibly face”. After reading the hints, I still couldn’t get a clue. However, there are some great explanation on the discussion forum A and B. These answers really help me understand the problem.

It is important to “minimize the maximum loss you could possibly face”. If you choose a strategy, this strategy will need different amounts of money to deal with all possible guess numbers. The money for a guaranteed win is calculated for the worst case. A clear example is given in this discussion.


Assume n = 10, a strategy with a guarantee win can be described as a decision
tree.

                7
              /   \
            3       9
           / \     /  \
          1   5   8   10
          |   /\
          2  4  6

In the above example, what is the maximum loss for all guess numbers?

1: 7 + 3 = 10
2: 7 + 3 + 1 = 11
3: 7 = 7
4: 7 + 3 + 5 = 15
5: 7 + 3 = 10
6: 7 + 3 + 5 = 15
7: 0
8: 7 + 9 = 16 (worst case)
9: 7
10: 7 + 9 = 16 (worst case)

Thus, the maximum loss is $16.

An important observation:

maxloss(7) = 7 + max(maxloss([1..6]), maxloss([8..10]))

maxloss(3) = 3 + max(maxloss([1..2]), maxloss([4..6]))

maxloss(9) = 9 + max(maxloss([8]), maxloss([9]))

and so forth ...

This is an important sub-problem structure for DP problems.

Our task is to find the minimum of maximum loss among all possible strategies.

Assume the guess number is in 1..n. We choose k as the first split number where k can be any number between 1 and n. So we can get the following sub-problem relationship:

minimax(1,n) = min([k + max(minimax(1,k-1), minimax(k+1,n)) for k in 1..n])

I convert it into code:

However, this recursive solution is time-consuming. With the memorization technique, I come up the following solution:

This solution is accepted by the online judge system. But function calls require a lot amount of space. So I convert the code to a DP solution without using recursion:

In summary, recursion -> memorization -> DP is a common strategy to incrementally improve your solution to solve a DP problem. The key of a DP problem is to find out the sub-problem structure or relationship.