题目:给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

// 输入: 2
// 输出: 1
// 解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

// 输入: 10
// 输出: 36
// 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：2 <= n <= 58

思路分析

本题可以通过动态规划和贪心算法来解决，不过贪心算法是最快的。

方法一：动态规划

题目明确说明n是大于1的整数。我们假定长度为n的绳子可以分成多少段为一个状态数组即dp[i]:也就是说数字i拆分为至少二个正整数之和的最大乘积，因此我们可以知道该状态数组的长度为n + 1,并且我们默认都给数组每一项初始化为1。同样的由于数字i至少拆分二个正整数之和，我们就假定拆分成2个正整数，那么我们就需要2个循环。

很显然当n<=3的时候dp[2] = 1,也因此我们可以从3开始循环，当n停止，而第二个循环也就是内层循环，我们从1开始，到i之前停止。也就是说数字i就被拆分成了j + (i - j)。例如数字9代表绳子的长度，那么9可以被拆分成1 + (9 - 1),很显然1 * 8不一定是它的最大乘积，那么我们可以再考虑，首先是分了一段为1的，也就是从dp[2]开始分的，那么(i - j)再分的话，就应该得到最大段数为dp[i - j]，也就可以知道j * dp[i - j]为再划分的乘积。从而得到了状态转移方程为max(dp[i],j * (i - j),j * (dp[i - j]))。

代码如下:

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    // 创建长度为n+1，并且每一项都是1的数组
    let arr = new Array(n + 1).fill(1);
    for(let i = 3;i <= n;i++){
        for(let j = 1;j < i;j++){
            arr[i] = Math.max(arr[i],j * (i - j),j * arr[i - j]);
        }
    }
    return arr[n];
};

以上算法的时间复杂度和空间复杂度分析如下:

• 时间复杂度：O(n ^ 2)。
• 空间复杂度：O(n)。

方法二:贪心算法

前面提到：8 拆分为 3+3+2，此时乘积是最大的。然后就推测出来一个整数，要拆成多个 2 和 3 的和，保证乘积最大。原理很容易理解，因为 2 和 3 可以合成任何数字，例如5=2+3，但是5 < 2 * 3；例如6=3+3，但是6 < 3 * 3。所以根据贪心算法，就尽量将原数拆成更多的 3，然后再拆成更多的 2，保证拆出来的整数的乘积结果最大。

但上面的解法还有不足。如果整数 n 的形式是 3k+1，例如 7。按照上面规则，会拆分成“3 + 3 + 1”。但是在乘法操作中，1 是没作用的。此时，应该将 1 和 3 变成 4，也就是“3 + 3 + 1”变成“3 + 4”。此时乘积最大。

综上所述，算法的整体思路是：

• n 除 3 的结果为 a，余数是 b
• 当 b 为 0，直接将 a 个 3 相乘
• 当 b 为 1，将（a-1）个 3 相乘，再乘以 4
• 当 b 为 2，将 a 个 3 相乘，再乘以 2

代码如下:

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    if(n < 4){
        return n - 1;
    }else{
        let a = Math.floor(n / 3),
            b = n % 3;
        switch(b){
            case 0:
                return Math.pow(3,a);
            case 1:
                return Math.pow(3,a - 1) * 4;
            case 2:
                return Math.pow(3,a) * 2;
        }
    }
};

以上算法的时间复杂度和空间复杂度分析如下:

• 时间复杂度：O(1)。
• 空间复杂度：O(1)。

更多思路。