# Dynamic Programming – Rod Cutting Problem

**Objective: **Given a rod of length n inches and a table of prices p_{i}, i=1,2,…,n, write an algorithm to find the maximum revenue r_{n} obtainable by cutting up the rod and selling the pieces.

This is very good basic problem after fibonacci sequence if you are new to Dynamic programming. We will see how the dynamic programming is used to overcome the issues with recursion(Time Complexity).

**Given**: Rod lengths are integers and For i=1,2,…,n we know the price p_{i} of a rod of length i inches

**Example:**

Length | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Price | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |

for rod of length: 4 Ways to sell : • selling length : 4 ( no cuts) , Price: 9 • selling length : 1,1,1,1 ( 3 cuts) , Price: 4 • selling length : 1,1,2 ( 2 cuts) , Price: 7 • selling length : 2,2 ( 1 cut) , Price: 10 • selling length : 3, 1 ( 1 cut) , Price: 9

**Best Price for rod of length 4: 10**

**Approach:**

**Naive Approach : Recursion**

- There can be n-1 cuts can be made in the rod of length n, so there are 2
^{n-1 }ways to cut the rod. - So for every length we have 2 options either we cut it or not. we will consider both the options and choose the optimal out of it.

**Code**:

**Time Complexity**: O(2^n-1)

But this time complexity is very high since we are solving many sub problems repeatedly.

**Dynamic Programming: Bottom-Up**

Instead of solving the sub problems repeatedly we can store the results of it in an array and use it further rather than solving it again.

See the Code for better explanation:

**Code**:

Result: Max profit for length is 5:11

**Reference: Link**