面试题14- I. 剪绳子

[fireairforce]

可以用完全背包的解法来做 & 也可以找规律

/**
 * @param {number} n
 * @return {number}
 */

var cuttingRope = function(n) {
    if(n === 2) {
        return 1;
    } 
    if(n === 3) {
        return 2;
    }
    let temp = [];
    for(let i = 1;i<=n;i++) {
        temp.push(i);
    }
    let dp = Array(n+1).fill(-1);
    dp[0] = 1;
    for(let i = 0;i<n;i++) {
        for(let j = temp[i];j<=n;j++) {
            dp[j] = Math.max(dp[j],dp[j - temp[i]] * temp[i])
        }
    }
    return dp[n];
};

找规律:

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    if(n === 2) {
        return 1;
    } 
    if(n === 3) {
        return 2;
    }
    let sum = 1;
    while(n > 4) {
      sum = sum * 3;
      n -= 3;
    }
    return sum * n;
};

[fireairforce]

n值要是很大的话，就只能找规律了~