Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.
Examples:
Input: n = 2
Output: 1 (Maximum obtainable product is 1*1)
Input: n = 3
Output: 2 (Maximum obtainable product is 1*2)
Input: n = 4
Output: 4 (Maximum obtainable product is 2*2)
Input: n = 5
Output: 6 (Maximum obtainable product is 2*3)
Input: n = 10
Output: 36 (Maximum obtainable product is 3*3*4)
1) Optimal Substructure:
This problem is similar toRod Cutting Problem.We can get the maximum product by making a
cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.
Let maxProd(n) be the maximum product for a rope of length n. maxProd(n) can be written as following.
maxProd(n) = max(i*(n-i), maxProdRec(n-i)*i) for all i in {1, 2, 3 .. n}
2) Overlapping Subproblems
Following is simple recursive C++ implementation of the problem. The implementation simply follows the recursive structure mentioned above.
A Tricky Solution:
If we see some examples of this problems, we can easily observe following pattern.
The maximum product can be obtained be repeatedly cutting parts of size 3 while size is greater than 4, keeping the last part as size of 2 or 3 or 4. For example,
n = 10, the maximum product is obtained by 3, 3, 4. For n = 11, the maximum product is obtained by 3, 3, 3, 2. Following is C++ implementation of this approach.
package DP;
public class MaxProductCutting {
public static void main(String[] args) {
System.out.println(maxProdRec(10));
System.out.println(maxProdDP(10));
System.out.println(maxProdTrick(10));
}
public static int maxProdRec(int n){
if(n==0 || n==1){
return 0;
}
int max = 0;
for(int i=1; i<n; i++){
// 1.只切一刀 2.切完一刀后,把余下的继续切
int bigger = Math.max(i*(n-i), i*maxProdRec(n-i));
max = Math.max(max, bigger);
}
return max;
}
// Time: O(n^2), space:O(n)
public static int maxProdDP(int n){
// maxProd[i]: 总长度为i的绳子能切出的最大乘积
int[] maxProd = new int[n+1];
maxProd[0] = maxProd[1] = 0;
// Build the table maxProd[] in bottom up manner and return
// the last entry from the table
for(int i=1; i<=n; i++){ // 总长度为i
int max = 0;
for(int j=1; j<=i/2; j++){ // 切长度为j
int bigger = Math.max(j*(i-j), j*maxProd[i-j]);
max = Math.max(max, bigger);
}
maxProd[i] = max;
}
return maxProd[n];
}
// 规律:不断以3为单位长度切
public static int maxProdTrick(int n){
if(n==2 || n==3){ // n equals to 2 or 3 must be handled explicitly
return n-1;
}
int res = 1;
while(n > 4){ // Keep removing parts of size 3 while n is greater than 4
n -= 3;
res *= 3; // Keep multiplying 3 to res
}
return n*res; // The last part multiplied by previous parts
}
}
分享到:
相关推荐
试设计一个算法,对于给定的I和k,求出I的最大k乘积。 编程任务: 对于给定的I 和k,编程计算I 的最大k 乘积。 需求输入: 输入的第1 行中有2个正整数n和k。正整数n是序列的长度;正整数k是分割的段数。接下来的一行...
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...
对DP问题中的最大m字段和问题进行ppt演示讲解
KDP晶体切削机理的实验研究,张飞虎,张超,KDP晶体是一种用于惯性约束核聚变中重要的非线性光学材料。传统光学研抛方法已不适用于加工KDP晶体,而单点金刚石飞刀切削由于其物
区间DP概率DP树形DP插头DP,每种DP一道典型例题,有助于初学者
1. 同一项目中S7-1200 与 S7-300 集成 DP 口之间 DP 主从通信,S7-1200 通过CM1243-5作为 DP 主站,S7-300 集成 DP 口作为 DP 从站; 2. 不同项目中S7-1200 与 S7-300 集成 DP 口之间 DP 主从通信,S7-1200 通过CM...
得宝 迪普乐DP-F850 DP-F650 DP-F620 DP-F550 DP-F520 制版印刷一体机 维修手册
蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A...
ASL CS5523是MIPI DSI输入、DP/e DP输出转换芯片。MIPI DSI最多支持4个通道,每个通道的最大运行速度为1.5Gps。对于DP 1.2输出,它由4个数据通道组成,支持1.62Gbps和2.7Gbps的链路速率。支持1.62Gbps和2.7Gbps的...
DP83848中文数据手册 DP83848中文文档 全篇翻译无排版 DP83848C / I / VYB / YB PHYTER™QFP单端口10/100 Mb / s以太网物理层收发器 从–40°C到105°C的多个温度范围•IEEE 802.3 ENDEC,10BASE-T收发器和 • 低...
内容: 数塔 最长不下降序列 乘积最大问题 以及PASCAL详细代码
DP接口介绍 1、 DP接口简介 2、 DP接口分类 2.1 标准DP接口 2.2 Mini-DP接口 3、 DP版本迭代 3.1 DP 1.0版本 3.2 DP 1.1a版本 3.3 DP 1.2版本 3.4 DP 1.3版本 3.5 DP 1.4版本 3.6 DP 2.0版本 3.7 版本对比 4、 DP...
区间dp课程ppt。内容包含石头合并1、2,删除字符串、最大回文数、能量项链、乘积最大问题,等区间dp重要内容。
Android中的长度单位详解(dp、sp、px、in、pt、mm).pdf
VESA官网的DP1.4标准协议
Android 蓝牙 A2dp 听歌卡音?audio数据到a2dp通道流程解析----A2dp流控原理(Acl Flow Control),一文搞懂蓝牙卡音问题处理
2 DP软件的文件结构 4 2.1 DP软件的配置信息 4 2.2 DP软件的执行程序 4 2.3 DP软件的内部数据库 4 3 DP软件的后台进程 5 3.1 DP软件的自动启动配置 5 3.2 DP软件的手工启动方法 5 3.3 DP软件的后台进程 5 4 DP软件...
适用于RD-EB、RD-ET、RD-EZ、RD-EB-MX、RD-ET-MX、RD-EZ-MX、KRD-EB、KRD-ET、KRD-EZ、KRD-EB-MX、KRD-ET-MX、KRD-EZ-MX 、SRD-R100、Q3-R100、Q3-R101、Q3-R102、DP-R103、DP-R 113、DP-R123、DP-R133、DP-R143、...