题目：给你一根长度为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,3...,n-1。因此f(n) =max(f(i) * f(n-i))，其中0<i<n。
这里注意：f(n) = max(f(i) * f(n-i)) ，fn是所有可能的f(i) * f(n-i)的最大值，其中0<i<n。
这是一个从上至下的递归公式。由于递归会有很多重复的子问题，从而有大量不必要的重复计算。一个更好的办法是按照从下到上的顺序计算，也就是说我们先得到，
再得到
，
，直到得到
。
/**
* 动态规划
*
* @param length 绳子的长度
* @return
*/
public static int maxProduceAfterCutting(int length) {
//异常情况
if (length < 2) {
return 0;
}
//绳子剪成m段，m>1 ,所以我们得剪成 1 * 1
if (length == 2) {
return 1;
}
//长度为3，只能剪成 1*2 最长的一段
if (length == 3) {
return 2;
}
//上面分别返回了长度小于等于3时候的最优解，下面是计算长度大于3时候的情况
//注释1处，定义一个数组，用来保存计算出来的子问题的最优解
int[] products = new int[length + 1];
products[0] = 0;
products[1] = 1;
//注释2处，
products[2] = 2;
//注释3处，
products[3] = 3;
int result = 0;
//开始计算
for (int i = 4; i <= length; i++) {
int max = 0;
//注释4处，直接从j=1开始，不需要从0开始。
for (int j = 1; j <= i / 2; j++) {
int product = products[j] * products[i - j];
if (max < product) {
max = product;
}
}
products[i] = max;
}
result = products[length];
return result;
}
注释1处，定义一个数组，用来保存计算出来的子问题的最优解。products[i]表示长度为i的绳子剪成若干段之后隔断成都的乘积的最大值，即。
注释2处，为什么这里products[2]等于2？例如当绳子长度为3的时候，我们剪成两段，其中一段为2，一段为1。这样长度为2的那段最大值就是2，而不是1，因为这一段我们不需要再剪了。
注释3处，初始化的时候为什么products[3]=3？因为当length<=3的时候，我们直接返回了结果。如果整个绳子的长度为3，我们必须把绳子剪开，因为题目要求m>1，其中一段为2，另一段为1，这样结果就是2。当length>=4的时候，我们可以把绳子剪成两段，其中一段为3,另一段为１，这样长度为3的那一段的最大值就是3而不是2，因为这一段我们不需要再剪了。当然长度为4的最大值是剪成2和2的组合，我们已经存储了2的长度。
注释4处，直接从j=1开始，不需要从0开始。
贪婪算法
贪婪算法和动态规划不一样。当我们应用贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。贪婪算法需要用数学的方式证明每一步的贪婪选择是正确的。
贪婪算法
- 当 n>=5 时，尽可能多地剪长度为 3 的绳子
- 当剩下的绳子长度为 4 时，就把绳子剪成两段长度为 2 的绳子。
证明：书上的证明。。。
- 当 n>=5 时，可以证明
，并且
。也就是说，当绳子剩下长度大于或者等于 5 的时候，可以把它剪成长度为 3 或者 2 的绳子段。
- 当 n>=5 时，
，因此，应该尽可能多地剪长度为 3 的绳子段。
- 当 n=4 时，剪成两根长度为 2 的绳子，其实没必要剪，只是题目的要求是至少要剪一刀。
/**
*
* @param length 绳子的长度
* @return
*/
public static int maxProduceAfterCuttingGreedy(int length) {
if (length < 2) {
return 0;
}
if (length == 2) {
return 1;
}
if (length == 3) {
return 2;
}
//尽可能多的减去长度为3的绳子段，这个需要去证明，长度为3的段数越多乘积越大
int timesOf3 = length / 3;
//注释1处
if (length - timesOf3 * 3 == 1) {
timesOf3 -= 1;
}
int timeOf2 = (length - timesOf3 * 3) / 2;
return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timeOf2);
}
注释1处，当绳子最后剩下的长度为4的时候，不能再减去长度为3的绳子段，此时更好的方法是把绳子减去长度为e的两段，因为2*2>3*1。
比如绳子长度为13:
- 尽可能减长度为3的绳子，可以剪4段长度为3的绳子，还剩一根长度为1的绳子，最终乘积是：
3*3*3*3*1 =81。 - 尽可能减长度为3的绳子，可以剪3段长度为3的绳子，当绳子最后剩下的长度为4的时候，不能再减去长度为3的绳子段，最终乘积是：
3*3*3*4 = 27 * 4 108。
参考链接：
