**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:**

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] = 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