题面

给你一根长度为 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。

答案须要取模 1e9+7（1000000007），如计算初始后果为：1000000008，请返回 1。

示例 1：

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

示例 2:

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

提醒：

• 2 <= n <= 1000

原题链接

剖析

该题在第 14 题“剪绳子”的根底上，减少了大数取余局部，上面探讨 C ++ 的 4 种解题思路：

动静布局、数学推导、数学推导优化、贪婪。

最初会再次印证一句古老的话：艺术与迷信终将在某一点相遇

1 动静布局（行不通）

在第 14 题代码根底上，每次从第 i - 1 个状态计算第 i 个状态时，退出取余运算，会得出谬误的后果。理由如下：

动静布局的特点是，第 i 个状态依赖于第 i - 1 个状态，最初一个状态（指标状态）依赖于倒数第二个状态，如果在状态转移间进行取余，会呈现有的转移须要取余，有的转移不须要取余：

假如 a 和 b 是两个数，a>b，a 须要取余，b 不须要取余，a 取余之后的值为 a1，可能呈现 a1<b 的状况，这就会误导前面的状态转移，最终导致谬误的后果。

这是无奈得出正确后果的动静布局的代码，留神，为了不产生溢出，须要将 dp 数组和若干两头值改成 long 类型（详见代码正文）：

class Solution {
public:
int cuttingRope(int n)
{
    int base = 1000000007;
    if(n==2)
    {return 1;}
    if(n==3)
    {return 2;}
    // 将 dp 数组改成 long 类型
    long dp[n+1][n+1];
    for(int i=0; i<n+1; i++)
    {for(int j=0; j<n+1; j++)
        {dp[i][j] = -1;
        }
    }
    for(int i=0; i<n+1; i++)
    {dp[i][i] = 1;
        dp[i][1] = i;
    }

    
    //dp[i][j], 长度为 i 的绳子，切成 j 段，乘积的最大值
    for(int tmp=3; tmp<=n; tmp++)
    {
        int now_len = tmp;
        for(int sp=2; sp<now_len; sp++)
        {
            int split = sp;
            // 将 x1 改成 long 类型
            long x1 = 1;
            // 将 dp 数组候选值 tmp_max 改成 long 类型
            long tmp_max = -1;
            bool overflow = false;
            while((x1<now_len) && (now_len-x1)>=(split-1))
            {
                // 将乘积 multi 改成 long 类型
                long multi = (x1*dp[now_len-x1][split-1]);
                if(!overflow){if(multi>base){
                        multi = multi%base;
                        tmp_max = multi;
                        overflow = true;
                    }
                    else{if(multi>tmp_max){tmp_max = multi;}
                    }
                }
                else{if(multi>base){
                        multi = multi%base;
                        if(multi>tmp_max){tmp_max = multi;}
                    }
                }
                x1++;
            }
            dp[now_len][split] = tmp_max;
        }
    }
    
    
    int final_max = -1;
    for(int p=1; p<=n; p++)
    {if(dp[n][p]>final_max)
        {final_max = dp[n][p];
        }
    }
    return final_max;
}
};

2 数学推导

务必先看此处的数学推导过程。

要点如下：

1. 对 n%3 的值进行分类探讨
2. 写出一个递归求余的函数

代码如下（正文局部即为思路）：

class Solution {
public:
    
    // 递归求余的函数
    long figure(int k){
        // 特判，边界条件
        if(k==0){return 1;}
        
        // 特判，边界条件
        if(k==1){return 3;}
        // 留神 temp 的值必须为 long，否则 leetcode 上会报溢出的谬误
        long temp = (3*figure(k-1));
        return temp%1000000007;

    }
    
    // 分类探讨的函数
    int cuttingRope(int n) {
        // 特判，n== 2 时返回 1
        if(n==2){return 1;}
        // 特判，n== 3 时返回 2
        if(n==3){return 2;}
        
        // 利用整除向下取整的个性，不论 n%3 是多少，k 总是咱们须要的值
        int k = n/3;
        long res = 0;

        
        if(n%3==0){
            // 把绳子宰割成 k 段，每段长度为 3
            res = figure(k)%1000000007;
        }

        else if(n%3 == 2){if(k==0){
                // 此处只能是 n =2
                res = 1;
            }
            else{long mid = (figure(k))*2;
                res = mid%1000000007;
            }
        }

        else{if(k==0){
                // 此处只能是 n =1，其实这一句能够不必，因为题目要求 n >1
                res = 1;
            }
            else{long mid = (figure(k-1))*4;
                res = mid%1000000007;
            }
        }
        int result = res;
        return result;
    }
};

提交后果：

3 数学推导优化

下面的代码，能够用四个字概括它的特点：又臭又长

一堆 if-else 语句，这样写代码到了前期很难保护。

进一步推导，齐全能够

对这根绳子一次切 3 个长度，一次切 3 个长度，当残余长度小于某个值时，再分类探讨。

代码如下（正文局部即为思路）：

class Solution {
public:
    int cuttingRope(int n) {
        int base = 1000000007;
        //res 的类型必须设置为 long，否则会溢出
        long res = 1;
        // 特判
        if(n<3){return 1;}
        // 特判
        if(n==3){return 2;}
        
        // 这里必须是 n >5，因为 n%3 的余数可能是 0、1、2
        // 0 是咱们最想要的后果，不必思考非凡状况
        //n%3= 1 时，最初一次切 3 之前，绳子长度为 4，这时咱们应该把 4 分成 2 +2, 而不是 1 +3, 因为(2*2)>(1*3)
        //n%3= 2 时，最初一次切 3 之前，绳子长度为 5，这时咱们应该把 5 分成 3 +2
        // 所以当绳子目前的长度大于 5 时，能够轻易切 3，然而当等于 5 或者小于 5 时，就要分类探讨了
        while(n>5){res = (res*3)%base;// 循环取余，避免溢出
            n = n-3;
        }
        int fi;
        // 最初一次切 3 之前，绳子长度为 5，这时咱们应该把 5 分成 3 +2,3*2=6, 故 fi=6
        if(n==5){fi = 6;}
        // 最初一次切 3 之前，绳子长度为 4，这时咱们应该把 4 分成 2 +2,2*2=4, 故 fi=4
        if(n==4){fi = 4;}
        // 最初一次切 3 之前绳子长度为 3，咱们不应该分这根绳子, 故 fi=3
        if(n==3){fi = 3;}
        return (res*fi)%base;
    }
};

提交后果：

贪婪

下面的代码，简洁了很多，然而，从提交成果上看，和没有优化之前并无差别，为什么呢？

留神到，下面的代码在 while 循环之后，有 3 个 if 判断语句 ，编译器在底层，会对 if 语句的走向，进行 猜想，但 if 的判断都是 == 判断，所以，编译器此时的猜想毫无意义，会节约很多工夫。

再去看一看下面的代码，咱们会发现，当 n <4 的时候，返回的都是 n -1；当 n = 4 的时候，返回的是 4。当 n = 5 的时候，就要进行惯例 切 3 操作。

好，再去看下面代码中最初一部分：

        while(n>5){res = (res*3)%base;// 循环取余，避免溢出
            n = n-3;
        }
        int fi;
        // 最初一次切 3 之前，绳子长度为 5，这时咱们应该把 5 分成 3 +2,3*2=6, 故 fi=6
        if(n==5){fi = 6;}
        // 最初一次切 3 之前，绳子长度为 4，这时咱们应该把 4 分成 2 +2,2*2=4, 故 fi=4
        if(n==4){fi = 4;}
        // 最初一次切 3 之前绳子长度为 3，咱们不应该分这根绳子, 故 fi=3
        if(n==3){fi = 3;}
        return (res*fi)%base;

while 循环的条件：n>5。如果：

咱们把它改成 n>4，去掉 while 循环前面的 3 个 if 语句，将最初一行return (res*fi)%base; 改成return (res*n)%base;，咱们会发现，再最终后果上，不会有任何变动，为什么不会有任何变动呢？持续剖析：

while 循环退出时，n 有以下几种状况：

1. n=4，最初一次切完 3，绳子长度为 4，这时咱们应该把 4 分成 2 +2,2*2=4，恰好就是绳子自身的值。
2. n=3，最初一次切完 3，绳子长度为 3，这时咱们不应该分这根绳子，放弃绳子自身的值。
3. n=2，最初一次切完 3，绳子长度为 2，阐明最初一次切 3 之前，绳子的长度为 5，对于 5，咱们应该把 5 分成 3 +2，而 2 恰好就是目前绳子自身的值。

综上所述，优化代码如下：

class Solution {
public:
    int cuttingRope(int n) {
        int base = 1000000007;
        long res = 1;
        if(n<4){return n-1;}
        if(n==4){return 4;}
        while(n>4){res = (res*3)%base;
            n = n-3;
        }
        return (res*n)%base;
    }
};

提交后果：

能够发现，执行工夫显著升高了，因为 while 循环前面没有那一大堆 if 判断了。

如果有好好看此处的数学推导，会发现，下面的代码，齐全能够依照 贪婪法的逻辑 去了解。

艺术与迷信终将在某一点相遇

Good luck!