Try One dimension DP

  • 0

    There are two dimensions DP Solutions so far, and their time complexity is O(n3). I tried an One dimension DP whoes time complexity is O(n2).

    The code partially passed. It passed 10/13 test cases. FYI.

    It would be great if anyone know how to modify the code to pass all test cases.


    public int getMoneyAmount(int n) {
        int[] guess = new int[n+1];
        int[] count = new int[n+1];
        for (int i=2; i<=n; i++){
            guess[i] = Integer.MAX_VALUE;
            count[i] = Integer.MAX_VALUE;
            for (int pos = 1; pos<=i; pos++){                
                /*split at pos, left guess[pos-1], right guess[i-pos] (need shift)
                int left = guess[pos-1],
                    right = shift(guess[i-pos], count[i-pos], pos);
                int splitCost = pos + Math.max(left, right); 
                if (splitCost <= guess[i]){
                    guess[i] = splitCost;
                    count[i] = Math.min(count[i], 1 + Math.max(count[pos-1], count[i-pos]));
        return guess[n];
    int shift(int sum, int n, int offset){
        sum += offset * n;
        return sum;


Log in to reply

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