# O(n^3) java, short explanation

• For me at first sight it seemed that the problem can be solved by using binary search for worse case. For example n=100. I supposed that picked number is 100 and tried to reach that 100 by binary search at first 50 then 75 etc. Then I noticed that binary search technique not always gives correct answer. Then come up with dynamic programming solution. For example to calculate the answer for n=100, left = 1 and right =n; then between this left and right we can run loop to know the best answer for left part and right part from i and get their minimum. This solution works for n^3 time and n^2 memory

``````public class Solution {
public int getMoneyAmount(int n) {
int dp[][] = new int[n+2][n+2];
for (int len=1; len<n; len++) {
for (int start=1; start+len<=n; start++) {
int end = start+len;
dp[start][end] = Integer.MAX_VALUE;
for (int pivot=start; pivot<=end; pivot++) {
int val = pivot + Math.max(dp[start][pivot-1], dp[pivot+1][end]);
dp[start][end] = Math.min(dp[start][end], val);
}
}
}
return dp[1][n];
}
}
``````

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