**Objective: **Given a rope of length n meters, write an algorithm to cut the rope in such a way that product of different lengths of rope is maximum. At least one cut has to be made.

**Note**: Assume that the length of rope is more than 2 meters, since at least one cut has to be made.

This is yet another problem where you will see the advantage of dynamic programming over recursion. I will show you how by storing and reusing the results of sub-problems will reduce the complexity of an algorithm significantly. These kind of questions are asked in interview’s like Amazon, Microsoft, Google etc.

**Example:**

• Rope length: 2 • Options: (1*1) • Maximum Product Cutting : 1*1 = 1 • Rope length: 3 • Options: (1*1*1, 2*1) • Maximum Product Cutting : 2*1 = 2 • Rope length: 4 • Options: (1*1*1*1, 2*1*1, 3*1, 2*2) • Maximum Product Cutting : 2*2 = 4 • Rope length: 5 • Options: (1*1*1*1*1, 2*1*1*1, 3*1*1, 2*2*1, 3*2) • Maximum Product Cutting : 3*2 = 6

**Approach:**

**Using Recursion:**

This problem is similar to “**Rod Cutting Problem**“.

- Check the products of all possible cuts can be made in the rope and return the maximum product.
- Since for every length there are two options, either a cut to be made or not. Solve the problem for both options and choose maximum.
- After Making the cut the further options are , Either this cut will produce the max product OR we need to make further cuts

**Recursive Equation:**

Let MPC(n) is the maximum product for length n.

(After Making the cut the further options are , Either this cut will produce the max product OR we need to make further cuts).**MPC(n) = max(i*(n-i), i*MPC(n-i)) for all (i=1,2…..n)**

**Time Complexity: O(2 ^{n}).**

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class MaximumProductCutting { | |

public int maxProdutRecursion(int n) { | |

// base case | |

if (n == 0 || n == 1) { | |

return 0; | |

} | |

// make all possible cuts and get the maximum | |

int max = 0; | |

for (int i = 1; i < n; i++) { | |

// Either this cut will produce the max product OR | |

// we need to make further cuts | |

max = Math.max(max, | |

Math.max(i * (n – i), i * maxProdutRecursion(n – i))); | |

} | |

//return the max of all | |

return max; | |

} | |

public static void main(String[] args) throws java.lang.Exception { | |

MaximumProductCutting i = new MaximumProductCutting(); | |

System.out.println("Maximum Product: "+i.maxProdutRecursion(10)); | |

} | |

} |

**But yet again we are solving many sub problems repeatedly. **

**Dynamic Programming: **

We will solve this problem in **Bottom-Up manner**.

We will store the solutions for sub problems when it getting solved for the first time and use it again in future so that we don’t have to solve again.

**Time Complexity :** O(N^2)

See the Code for better understanding.

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class MaximumProductCutting { | |

public void maxProductCutting(int n) { | |

int[] MPC = new int[n + 1]; | |

MPC[1] = 1; | |

for (int i = 2; i < n + 1; i++) { | |

int mp = Integer.MIN_VALUE; | |

for (int j = 1; j < i; j++) { | |

mp = Math.max(mp, Math.max(j * MPC[i – j], j * (i – j))); | |

} | |

MPC[i] = mp; | |

} | |

System.out.println("Dynamic Programming: Maximum product cutting in " | |

+ n + " is: " + MPC[n]); | |

} | |

public static void main(String[] args) throws java.lang.Exception { | |

MaximumProductCutting i = new MaximumProductCutting(); | |

i.maxProductCutting(10); | |

} | |

} |

Output: Dynamic Programming: Maximum product cutting in 10 is: 36

why we use Math.max(j * MPC[i – j], j * (i – j)));

we can get right answer by using mp=Math.max(mp,j * MPC[i – j]); also

what is the time complexity for this Bottom up approach ?

Its O(N^2), I have updated the post.