We are playing the Guessing Game. The game will work as follows:
- I pick a number between 1 and n.
- You guess a number.
- If you guess the right number, you win the game.
- If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
- Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
So, it's still binary search? nope, the first example tell me is not a simple binary searching. The money seem to we shall choose a bigger number first, because it cost more money. 1 + 2 + 3 ... 9 = 45; 45 / 2 = 22.5 => 1 + .. 7 = 28 > 22.5; So maybe, we shall choose mid of sum value.
Nope...it's a DP. the std use a DP[i][j] to represent guess one number between i and j, the minimum cost we shall use. And let us see an example
1 2 3 4;
first we will update dp[j][i] by max(dp[j][k-1],dp[k+1][j]) + k which means we guess k and use the maximum cost (becuase it's a minmax problem), if we want answer we need maximum cost. After all these k, we will choose a minimum k.
And another problem, why we need to use i = 2 - n and j = (i - 1) - 0?
because we can know that, we only will know that [1..i] => [1..i+1], thus [1..i] <== [i-1,i] thus we use this order.