题目
给你一根长度为n的绳子，请把绳子剪成m段(m,n都是整数,n>1并且m>1)，每段绳子的长度j
记为k[0],k[1],…k[m]。请问k[0]* k[1]*…*k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
分析
动态规划
长度n的绳子，我们剪第一刀的时候有(n-1)种方法。分别为：1，2，3，…，n-1。
这是一个自顶向下的递归，在之前剑指Offer - 面试题10：斐波那契数列中讲过从上往下，复杂度是以n的指数增长。
当绳子长度为1时，不需要剪。f(1) = 1；
当绳子长度为2时，只能剪成1、1。f(2) = 1；
当绳子长度为3时，有俩种剪法，一是剪三刀，1、1、1。二是剪俩刀1、2。最大值为2；f(3) = 2；
当绳子长度为4时，有三种剪法，一是1、1、1、1。二是2、1、1。三是2，2。最大值为4。f(4) = 4；
得出公式f(n) =max(f(i)*f(n-i));所以我们从下向上，用一个临时数组保存当前长度的最大乘积的结果。
C
#include<stdio.h> #include<stdlib.h> int maxProductAfterCutting_solution(int length) { if (length < 2)// 0 1 { return 0; } if (length == 2)//(1,1) { return 1; } if (length == 3)//(2,1) { return 2; } int i = 0; int j = 0; //存放当前下标长度的最大乘积 int* p = (int*)malloc(sizeof(int) * (length + 1)); if (NULL == p) { perror("空间申请失败！"); exit(EXIT_FAILURE); } p[0] = 0; p[1] = 1; p[2] = 2; p[3] = 3; for (i = 4; i < length + 1; i++) { int max = 0; for (j = 1; j <= i / 2; j++)// 1 3 22 2 { if (max < p[j] * p[i - j]) { max = p[j] * p[i - j]; } } p[i] = max; } int ret = p[length]; free(p); return ret; } int main() { int ret = maxProductAfterCutting_solution(10); printf("长度为10的绳子剪完最大乘积为：%d\n", ret); return 0; }
length = 10;最大是332*2=36
优化动态规划
总结：我们可以发现任何大于3的n都可以拆分为数字1，2，3的和。因此我们可以用三个变量动态存储这些数据。这样得到空间复杂度就成了常量级O(1)。
比如我们求9，有三种情况
1、剪1剩下的长度就是8，这时我们只需要比较8与第8次计算的结果哪个大，用哪个，然后大值* 1就是最大乘积
2、剪2剩下的长度就是7，这时我们只需要比较7与第7次计算的结果哪个大，用哪个，然后大值* 2就是最大乘积
3、剪3剩下的长度就是6，这时我们只需要比较6与第6次计算的结果哪个大，用哪个，然后大值* 3就是最大乘积
然后对这三种情况求的值取最大值即可
下面是max的定义（可参考）
C
#include<stdio.h> #include<stdlib.h> int maxProductAfterCutting_solution(int length) { int num[3] = { 0,1,1 }; int i = 0; for (i = 3; i < length + 1; i++) { num[i % 3] = max(max(1 * (num[(i - 1) % 3], i - 1), 2 * max(num[(i - 2) % 3], i - 2)), 3 * max(num[(i - 3) % 3], i - 3)); } return num[length % 3]; } int main() { int ret = maxProductAfterCutting_solution(10); printf("长度为10的绳子剪完最大乘积为：%d\n", ret); return 0; }
贪心+递归法
经过上述的众多分析，我们发现每次都剪长度为3的子段。
当剩余为6时，剪个三，剩下3就结束了。实际是刚好剪完
当剩余为5时，剪个三，剩下2就结束了。
当剩余为4时，剪个二，剩下2就结束了。
C
#include<stdio.h> int maxRecursion(int length) { if (length == 0)//刚好剪完了 { return 1; } if (length == 4)// 2 * 2 { return 4; } if (length == 5)//2 * 3 { return 6; } return 3 * maxRecursion(length - 3); } int maxProductAfterCutting_solution(int length) { if (length < 1) { return 0; } if (length == 2 || length == 1) { return 1; } if (length == 3) { return 2; } return maxRecursion(length); } int main() { int ret = maxProductAfterCutting_solution(10); printf("长度为10的绳子剪完最大乘积为：%d\n", ret); return 0; }
贪心+数学
思路：
我们直接让length对3求余，若发现剩余2，就让结果-1再保存。（因为要分成2、2）否则就直接将结果保存。
然后剩余的值可能为0-4。再让其对2求余，再保存。
maxnumber = pow(3,第一次求得结果) * pow(2，第二次求的结果)。
这样可以将时间复杂度降到O(1)，空间复杂度为O(1)。
C
#include<stdio.h> #include<math.h> int maxProductAfterCutting_solution(int length) { if (length < 1) { return 0; } if (length == 2 || length == 1) { return 1; } if (length == 3) { return 2; } int n3 = length % 3 == 1 ? (length / 3 - 1) : (length / 3);//剪成长度为3的子段有n3个 int n2 = length % 3 == 1 ? 2 : ((length % 3) / 2);//剩余长度剪成长度为2的子段有n2个 return (int)pow(3, n3) * (int)pow(2, n2); } int main() { int ret = maxProductAfterCutting_solution(10); printf("长度为10的绳子剪完最大乘积为：%d\n", ret); return 0; }
本章完！
