Problem: Given a rope with length n, how to cut the rope into m parts with length n[0], n[1], ..., n[m-1], in order to get the maximal product of n[0]*n[1]* ... *n[m-1]? We have to cut once at least. Additionally, the length of the whole length of the rope, as well as the length of each part, are in integer value.
Solution 1: Dynamic programming O(n*n)
Firstly let’s define a function f(n) for the maximal length product after cutting a rope with length n into parts. We have n-1 choice for the first cut on the rope, with the length of the first part 1, 2, … n-1 respectively. Therefore, f(n)=max(f(i)*f(n-i), where 0<i<n).
Also refer to http://www.geeksforgeeks.org/dynamic-programming-set-36-cut-a-rope-to-maximize-product/
Read full article from Coding Interview Questions: No. 52 - Maximal Product when Cutting Rope
Solution 1: Dynamic programming O(n*n)
Firstly let’s define a function f(n) for the maximal length product after cutting a rope with length n into parts. We have n-1 choice for the first cut on the rope, with the length of the first part 1, 2, … n-1 respectively. Therefore, f(n)=max(f(i)*f(n-i), where 0<i<n).
public static int maxProductAfterCutting_solution1(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 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];
}
Solution 2: Tricky cutting strategy O(1)
There is a strategy to cut the rope to get maximal product: We cut the parts with length either 3 or 2. Additionally, we try to keeping cut parts with length 3 as many as possible. Therefore, we could solve the problem with the following Java code:
public static int maxProductAfterCutting_solution2(int length) {
if(length < 2) {
return 0;
}
if(length == 2) {
return 1;
}
if(length == 3) {
return 2;
}
int timesOf3 = length / 3;
if((length - timesOf3 * 3) % 2 == 1) {
timesOf3 -= 1;
}
int timesOf2 = (length - timesOf3 * 3) / 2;
return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));
}
When n≥5, we could prove that 2(n-2)>n and 3(n-3)>n. Therefore, we continue to cut rope into parts with length 3 or 2 when the length is greater than 5. Additionally, 3(n-3) ≥ 2(n-2) when n≥5, so we cut parts with length 3 as many as possible.
The prerequisite of the proof above is n≥5. How about n is 4? There are only two approaches to cut when the length of the rope is 4: Cut into two parts with lengths 1 and 3, or with lengths 2 and 2. In our strategy, the rope will be cut into two parts with length 2 and 2.
Read full article from Coding Interview Questions: No. 52 - Maximal Product when Cutting Rope
