Javascript Solution with Explanation


  • 0
    S

    num -> dp[num]
    0 -> 0
    1 -> 1
    2 -> 1
    3 -> 2
    4 -> 4
    5 -> 6
    multiplier could be the number itself or number combination that sums up to the number. So choose whichever is larger.
    8 for example: max(dp[3], 3)max(dp[5], 5) --> 3dp[5] --> 323

    var integerBreak = function(n) {
        var dp = new Array(n+1).fill(0);
        dp[0] = 0;
        dp[1] = 1;
        for(var i = 2; i <= n; i++){
            for(var j = 1; 2*j <= i; j++){
                dp[i] = Math.max( dp[i], Math.max(j, dp[j])*Math.max(i-j, dp[i-j]) );
            }
        }
    
        return dp[n];
    };
    

Log in to reply
 

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