剑指Offer(书):剪绳子
题目:给你一根长度为n的绳子,请把绳子剪成m段,每段绳子的长度记为k[0],k[1]....,k[m]。请问k[0]xk[1]x...,k[m]可能的最大乘积是多少。例如:长度为8剪成2 3 3 得到最大乘积18.
分析:绳子的最小基础剪发可以分为2 或3, 也就是,当数据中全是由2 或3 组成时,相乘的结果最大。因此,由小至大,
* 绳子的长为2时,只能剪成1 1,即f(2) = 1x1 = 1;
* 当绳子长为3时,可能将绳子剪成长度为1 2 或者1 1 1,由于1 x 2 > 1 x 1 x 1,因此f(3)=2;
* 当绳子长为4时,可能将绳子剪成长度为2 2 或者 1 2 1 或者1 1 1 1或者 1 3,由于2 x 2 > 其他,因此f(4)=2*2
* 当绳子长为5时,可能将绳子剪成长度为3 2 或者...,由于3 x 2 > 其他,因此f(5)=3*2;
* 当绳子长为6时,可能将绳子剪成长度为3 3 或者...,由于3 x 3 > 其他,因此f(6)=3*3=9;//不使用f(3)因为3为最小单位中的最大值
* 当绳子长为7时,可能将绳子剪成长度为4 3 或者...,由于4 x 3 > 其他,因此f(7)=f(4)*3=2*2*3=12;我们的算法求解范围为由1-n。由小向大算,因此f(4)我们已经算出来了,直接使用即可,不必重复计算。
* 当绳子长为8时,可能将绳子剪成长度为2 6 或者...,因此f(8)=f(6)*2=3*3*2=18;我们的算法求解范围为由1-n。由小向大算,因此f(6)我们已经算出来了,直接使用即可,不必重复计算。
同理,当绳子长为9时,比较2*f(7)的值和3*f(6)的值即可.当绳子长为10时,比较2*f(8)的值和3*f(7)的值即可..当绳子长为11时,比较2*f(9)的值和3*f(8)的值即可.
public int maxProductAfterCutting(int length){
if(length<2){
return 0;
}
if(length==2){
return 1;
}
if(length==3){
return 2;
} int[] products = new int[length+1];
products[0]=0;
products[1]=1;
products[2]=2;
products[3]=3;
int max=0;
for(int i=4;i<=length;i++){
max=0;
for(int j=1;j<=i/2;j++){
int product =products[j]*products[i-j];
if(max<product) {
max = product;
}
}
products[i]=max;
}
return products[length];
}
这是另一种实现方式。按照最小基数单元来的。2 3,减少一点点计算次数。第一次感受到了算法的美妙之处~~~不要鄙视我,哈哈
public int maxProductAfterCutting(int length) {
if (length < 2) {
return 0;
}
if (length == 2) {
return 1;
}
if (length == 3) {
return 2;
} 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 p2 = 2 * products[i - 2];
int p3 = 3 * products[i - 3];
products[i] = p2 < p3 ? p3 : p2;
}
return products[length];
}
上面是动态规划法,下面是贪婪法。
public int maxProductAfterCutting2(int length) {
if (length < 2) {
return 0;
}
if (length == 2) {
return 1;
}
if (length == 3) {
return 2;
}
int paraThree = length / 3;
int paraTwo = 1;
if (length - paraThree * 3 == 1) {
paraThree--;
paraTwo = 2;
}
return (int) (Math.pow(3, paraThree)) * (int) (Math.pow(2, paraTwo));
}
最新文章
- Java多线程与静态方法
- 遍历List集合,删除符合条件的元素
- city-picker 选择省市县的一个控件,好用。
- 你需要知道的MySQL开源存储引擎TokuDB
- ES6 变量的解构赋值
- FWT
- 终极事务处理(XTP,Hekaton)——万能大招?
- jquery实现简单的ajax
- webpack echarts配置实例
- 模拟Vue之数据驱动3
- redux深入理解之中间件(middleware)
- Java学习点滴——初识Java
- 【easy】101. Symmetric Tree
- 大数据小白系列 —— MapReduce流程的深入说明
- Linux批量结束、杀死进程
- weblogic安装升级配置
- linux网络配置+远程工具使用
- ios开发中字符串的常用功能总结
- LeetCode(22):括号生成
- Intellij Idea 导入多个maven项目展示在左侧栏Maven Projects
热门文章
- fiddler安装及抓取http和https请求
- 51Nod 1116 K进制下的大数(暴力枚举)
- android ViewPager 与Fragment
- AtCoder Grand Contest 012 A
- BFS Codeforces Round #297 (Div. 2) D. Arthur and Walls
- (转)深入理解Java对象的创建过程
- Problem E: 穷游中国在统题 优先队列 + 模拟
- H5图片预览功能
- AJPFX总结Java 程序初始化过程
- Python behave in BDD