https://leetcode.com/problems/guess-number-higher-or-lower-ii/

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.

Hint:

1. The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.
2. Take a small example (n = 3). What do you end up paying in the worst case?
4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

#### java

https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation

Simple DP solution with explanation~~

For each number x in range[i~j]
we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}

–> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.

then we get DP([i~ j]) = min{xi, … ,xj }

–> // this min makes sure that you are minimizing your cost.

Here is a bottom up solution.

https://discuss.leetcode.com/topic/51358/java-dp-solution

Java DP solution

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]) }

https://discuss.leetcode.com/topic/51494/java-commented-dp-solution

Java commented DP solution

Big Idea: Given any n, we make a guess k. Then we break the interval [1,n] into [1,k - 1] and [k + 1,n]. The min of worst case cost can be calculated recursively as

cost[1,n] = k + max{cost[1,k - 1] + cost[k+1,n]}
Also, it takes a while for me to wrap my head around “min of max cost”. My understand is that: you strategy is the best, but your luck is the worst. You only guess right when there is no possibilities to guess wrong.

Any questions, suggestions & criticism welcomed!

#### cpp

https://discuss.leetcode.com/topic/51487/an-o-n-2-dp-solution-quite-hard

An O(n^2) DP Solution, Quite Hard.

Algorithm description: http://artofproblemsolving.com/community/c296841h1273742

#### python

https://discuss.leetcode.com/topic/51356/two-python-solutions

Two Python solutions

To find out how much money I need to win the range lo..hi (the game starts with the range 1..n), I try each possible x in the range (except hi, which is pointless because hi-1 costs less and provides more information), calculate how much I need when using that x, and take the minimum of those amounts.

Bottom-up dynamic programming:

Top-down with memoization, subclassing dict for convenience. Simpler than bottom-up because I don’t need to specify ranges/loops for lo and hi and don’t need to think about their orders and how big my DP matrix needs to be. On the other hand, it’s slower.

Got the motivation to use tuples as indexes from @agave. I had used that myself sometimes in the past, but thought it would be very slow. Turns out it’s not that slow. I should do some timings to get a better feeling for it…