Java DP solution


  • 0
    M
    public class Solution {
        public static int[] memo;
        public int integerBreak(int n) {
            if(memo == null){ 
                memo = new int[n + 10];
                memo[0] = 0;
                memo[1] = 1;
            }
            if(memo.length < n + 1){
                int[] temp = new int[(2*n) + 1];
                for(int j = 0; j < memo.length; j++){
                    temp[j] = memo[j];
                }
                memo = temp;
            }
            
            if(memo[n] != 0){
                return memo[n];
            }
            
            for(int k = 2; k <= n; k++){
                if(memo[k] == 0){
                    int max = 0;
                    for(int i = 1; i < k; i++){
                        int temp = (k - i) > memo[k - i] ?  
                                   (k - i) * i : memo[k - i] * i;
                        max = max > temp ? max : temp;
                    }
                    memo[k] = max;
                }
            }
            
            return memo[n];
        }
    }
    

    This solution uses memoization and amortized doubling on the memoized array. Something that gave me trouble was the fact that some n's have a solution which is smaller than n, which throws off larger solutions. That is the reason for checking if k - i > memo[k - i], otherwise i would be including 1's in the solution when there shouldn't be any.


Log in to reply
 

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