题面
给你一根长度为
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 数学推导
务必先看此处的数学推导过程。
要点如下：
- 对n%3的值进行分类探讨
- 写出一个递归求余的函数
代码如下（正文局部即为思路）：
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有以下几种状况：
- n=4，最初一次切完3，绳子长度为4，这时咱们应该把4分成2+2,2*2=4，恰好就是绳子自身的值。
- n=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!