题目
给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0]，k[1]，...，k[m]。请问k[0]k[1]
...
k[m]可能的最大乘积是多少？
例如：当绳子的长度为8时，我们把它剪成长度为2、3、3的三段，此时最大的乘积是18.
问题解析
- 问题是求最优解；
- 整体的问题的最优解是依赖各个子问题的最优解；
- 子问题之间还有互相重叠的更小的子问题；
- 为避免子问题的重复计算，我们存储子问题的最优解。从上往下分析问题，从下往上求解问题。
上面的几个条件可以看出，属于动态规划问题。
动态规划
首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。
在剪第一刀的时候，我们有n-1种可能的选择，也就是说剪出来的第一段的绳子的可能长度分别为1,2,...,n-1.因此 f(n) = max(f(i)f(n-i))，其中
0<i<n
这是一个从上至下的递归公式，由于递归会有很多重复的子问题，从而有大量不必要的重复计算。更好的办法是按照从下而上的顺序计算，也就是说我们先得到f(2)、f(3)，再得到f(4)、f(5)，直到得到f(n)
当绳子的长度为2时，只可能剪成长度为1的两段，因此f(2)=1。当绳子的长度为3时，可能把绳子剪成分别为1和2的两段或者长度都为1的三段，由于 1 x 2 > 1 x 1 x 1，因此f(3) = 2
C++算法实现
int maxProductAfterCutting_solution(int length) {
if(length < 2) // 长度小于2，不符合题意
return 0;
if(length == 2) // 长度为2，只有一种裁剪方案，剪成两段各为1，所以乘积为1
return 1;
if(length == 3) // 长度为3，最大乘积为2
return 2;
// 1 创建数组并初始化前4个元素
int *products = new int[length + 1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
// 2 从绳子长度为4开始遍历
for (int i=4; i<=length; i++) {
max = 0;
for (int j=1; j<=i/2; j++) { // 3 绳子的裁剪方案，计算最大值
int product = products[j]*products[i-j];
if (max<product)
max = product;
products[i] = max; // 记录对应长度的最大值
}
}
// 获取最大值
max = products[length];
delete[] products;
return max;
}
代码分析
代码中，子问题的最优解存储在数组products里。数组中第i个元素表示把长度为i的绳子剪成若干段之后各段长度乘积的最大值，即f(i)。但是这里需要排除长度小于等于3的情况，否则会产生困惑
当length<=3的时候，我们已经直接返回了结果。另外绳子长度小于等于3时，一刀都不剪的长度大于剪后的乘积，这些是特例，我们需要存储对应的值方便后续的遍历计算。从4开始，所有剪后的长度乘积都大于等于不剪的长度。
复杂度
时间复杂度为O(n²)，空间复杂度为O(n)
贪婪算法
- 贪婪算法在对问题求解时，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解；
- 选择的贪贪婪策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关；
策略：当n5时，尽可能多地剪长度为
3的绳子；当剩下的绳子长度为4时，把绳子剪成长度为2的绳子。
C++算法实现
int maxProductAfterCutting_solution2(int length) {
if (length < 2)
return 0;
if (length == 2)
return 1;
if (length == 3)
return 2;
// 尽可能多的剪去长度为3的绳子段
int timesOf3 = length / 3;
// 当绳子最后剩下的长度为4的时候，不能仔剪去长度为3的绳子段
// 此时更好的方法是把绳子剪成长度为2的两段，因为 2 x 2 > 3 x 1
if (length - timesOf3 * 3 == 1)
timesOf3 = 1;
int timesOf2 = (length - timesOf3 * 3) / 2;
return (int)(pow(3, timesOf3))*(int)(pow(2, timesOf2));
}
证明思路
首先，当n5的时候，我们可以证明先
2(n-2)>n。也就是说，当绳子剩下的长度大于等于5的时候，我们就把它剪成长度为3或者2的绳子段。另外，当n5时，3(n-3)
2(n-2)，因此我们应该尽可能地多剪长度为
3的绳子段。
前面证明的前提是n5。那么当绳子的长度为
4呢？在长度为4的绳子上剪一刀，有两种可能的结果：剪成长度分别为1和3的两根绳子，或者两根长度都为2的绳子。很明显是 2 x 2 > 3 x 1。
复杂度
时间、空间复杂度为O(1)
参考
《剑指offer》
