O(n^3) java, short explanation


  • 0
    A

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

Log in to reply
 

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