# Dynamic Programming – Maximum Product Cutting Problem.

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.

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

Time Complexity: O(2n).
Code:

 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:

 public class MaximumProductCutting { public void maxProductCutting(int n) { int[] MPC = new int[n + 1]; MPC = 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
```