前序
动态规划与贪婪算法
如果面试题是求一个问题的最优解（通常是最大值和最小值），而且该问题可以分解为若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题。
动态规划问题的第一个特点：求问题的最优解
第二个特点：整体问题的最优解依赖于子问题的最优解。
第三个特点：大问题可以分解为若干个小问题，小问题之间还有相互重叠的更小的子问题。
第四个特点：从上往下分析问题，从下往上求解问题
贪婪算法和动态规划不同，应用贪婪算法解决问题时，每一步都可以做出一个贪婪的选择，基于这个选择我们确定能够得到最优解。
题目
给你一根长度为n的绳子，把绳子剪成m段（m、n都是整数且m > 1, n > 1）,m段绳子的长度依然是整数，求m段绳子的长度乘积最大为多少？
- 比如绳子长度为8，我们可以分成2段、3段、4段...8段，只有分成3段且长度分别是2、3、3时能得到最大乘积18
动态规划的方式去解决，一共有n-1个分割方式去分割整体问题以及每一个子问题，设置一个长度为length+1的数组，记录各个分别为4到总长度为length的最大值，如果是长度2,3以及小于1，直接返回其唯一的选择乘积为1,2以及0。如果为4，则开始找最大乘积，记录在product中，product初始设置为各自的下标值，0，1，2，3。双重循环，第一层表示f(n)=max(f(i)×f(n-i))中的n（4-length），第二层是小于n的一半的数，也就是函数中的i，（1-n/2）
所以双重循环保证找出不同对的组合，每次取之前找到的相应位置的最大值，最后输出最后一位。
代码如下：
//时间复杂度为O(n2),空间复杂度为o(n)
public static int maxProductAfterCutting(int length) {
if (length<2){
return 0;
}
if (length==2){
return 1;
}
if (length==3){
return 2;
}
/**
* 多加一个长度，因为起始是从1开始
* 123位置上直接设置长度，4以后选用区域最大值，保证最大值是唯一的
*/
int[] products = new int[length+1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
for (int i=4;i<=length;i++){
int max = 0;
//一半有效
for (int j=1;j<=i/2;j++){
//得到max{f(i)*f(n-i)}
int product = products[j]*products[i-j];
if (product > max){
max = product;
}
}
//保存f(n)最大值
products[i] = max;
}
return products[length];
}
贪婪法
/**
* 时间和空间复杂度都为o(1)
* 数学证明：
* 1、当n<5时，我们会发现，无论怎么剪切，乘积product <= n，n为4时，product最大为2*2=4；
* 2、当n>=5时，可以证明2(n-2)>n并且3(n-3)>n。而且3(n-3)>=2(n-2)。所以我们应该尽可能地多剪长度为3的绳子段。
* 化成尽可能多的长度为3的段，其中如果最后余1，则留下一个3提供给1，组成4，最后计算乘积
* @param length
* @return
*/
public static int maxProductAfterCutting2(int length) {
if (length<2){
return 0;
}
if (length==2){
return 1;
}
if (length==3){
return 2;
}
//尽可能的找到可以分为多少个长度为3的段
int countof3 = length/3;
if (length%3 == 1){
countof3--;
}
int countof2 = (length-countof3*3)/2;
return (int)Math.pow(3,countof3)*(int)Math.pow(2,countof2);
}
public static void main(String[] args) {
System.out.println(maxProductAfterCutting(8));
System.out.println(maxProductAfterCutting2(8));
}
