Try One dimension DP


  • 0
    Y

    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.