整数拆分

[JesseZhao1990]

方法一

利用递归

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    var memo = new Array(n+1).fill(-1);
    
    function breakInteger(n){
        if(n===1) return 1;
        
        if(memo[n] != -1 ) return memo[n];
        
        var res = -1;
        for(var i=1;i<=n-1;i++){
            res = Math.max(res, i * (n-i), i * breakInteger(n-i))
        }
        memo[n] = res;
        return res;
    }
    
    return breakInteger(n);
    
};

方法二

利用动态规划

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

leetcode原题地址：https://leetcode-cn.com/problems/integer-break/description/