# 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.

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

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

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.