Think about this question for three days, read the hint, still had no thought, but minimax did help, finally got this O(n^3) DP solution. Thanks @yygy for correcting me.

Just use an example here for explaining how to find this approach.

Suppose n is 5, draw a tree to find the minimum cost in worst cases.

Through the tree, find the transition function:

- f(i,j) stands for the minimum lost between guessing i and j.
- f(i,0) = 0, f(i,i) = 0
- f(i, i) = 0
- f(i,i+1) = i
- f(i,j) = min[( k from i to j) max(k+f(i,k-1), k+f(k+1,j)]
- the answer for this problem is f(1,n)

Then find a way to calculate the final answer. Draw a square matrix, the value will be filled in like this:

Here is the code:

```
public int getMoneyAmount(int n) {
int[][] f = new int[n+2][n+2];
for(int i = 1; i < n; i++) f[i][i+1] = i;
for(int k = 1; k <= n-2; k++){
for(int left = n-k-1, right = n; right >= k+2; left--,right--)
{
int min = Integer.MAX_VALUE;
for(int i = left; i <= right; i++){
int max = Math.max(i+f[left][i-1], i+f[i+1][right]);
if(max < min) min = max;
}
f[left][right] = min;
}
}
return f[1][n];
}
```