# DP JAVA O(n^3) Solution With Explanation, 15ms, 17 lines

• 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];
}
``````

• @boyzhirui Why not O(n^3)?

• @boyzhirui When n=1000,it runs very slow, it's indeed O(n^3). This is a typical interval DP whose time complexity is general O(n^3).

• @yygy Yeah. I am sorry. You're right. Previously I thought the solution is O(n^3), but I changed the title after I woke up.

Since we need to fill in n^2 elements and each one will cost O(n), this solution should be O(n^3).

There may be a better way to solve the problem.

• @ZebraRabbit Nice drawing

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.