package cn.zxy.interview;
/**
* 分析:
* 动态规划典型题
* 例如要求长度为8的绳子怎么剪得到的乘积最大, 只需要算一层, 将绳子剪成两段
* 分别是(1,7) (2,6) (3,5) (4,4) 这里我们假设一个前提就是分成的这些小段乘积已经有最优解
* 只要是小段的乘积最大, 大段的乘积一定最大
* 这就是动态规划法的核心之一: 整体问题的最优解依赖于每个子问题的最优解
*
* 一个细节:
* 为什么要从4开始计算得到最优, 而不是大一点比如5, 也不是小一点比如3
* 因为从4以及4以后的数, 其分段最大乘积一定大于本身 分段求最优才有意义
* 比如5-->(2*3=6>5)
*
* 如果用递归 会出现子问题求解重复 因此使用循环
*/
public class A14_CutRope {
public static int maxProductAfterCutting(int length){
//边界情况 可以理解为无法用动态规划求出
if(length < 2) return 0;
if(length == 2) return 1;
if(length == 3) return 2;
//大于等于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++){
int temp = products[j] * products[i-j];
max = Math.max(max, temp);
}
products[i] = max;
}
return products[length];
}
/**
* 贪婪算法
* 尽可能多的剪去长度为3的绳子段
*
*/
public static int greedAlgs(int length){
if(length < 2) return 0;
if(length == 2) return 1;
if(length == 3) return 2;
int timesOf3 = length / 3;
//可能剩下0, 1, 2; 如果剩下1, 说明最后一剪子把长度为4剪成了1,3两段,
// 而剩余长度为4时剪成2,2结果才是最优的4>1*3
if((length - 3 * timesOf3) == 1){
timesOf3--;
}
//如果是0, timeOf2 = 0; 如果剩下是2, timeOf2 = 1
int timesOf2 = (length - 3 * timesOf3) / 2;
int max = (int)Math.pow(3, timesOf3) * (int)Math.pow(2, timesOf2);
return max;
}
public static void main(String[] args) {
int num = 24;
System.out.println(maxProductAfterCutting(num));
System.out.println(greedAlgs(num));
}
}
网友评论