### Cutting A Rod Problem

##### What is a best way to cut a rod of length of n meter into smaller pieces in to maximize the revenue.

**Formula:**

`Solve(n) = Max [price(n) + Solve(n-i-1) for all i in {0, 1, .... n-1}] `

##### Dynamic Programming Algorithm:

- Create DP table of size = n +1
- Set table[0] = 0
- Iterate i from 1 to n
- Set max = INFINITY
- Iterate j from 0 to 1
- Set max = Max {max, price [i] + table[i-j-1] }
- Set table[i] = max

- Return table[n]

Latest Source Code:

Github: CuttingRodProblem.java

**Output:**

Length: 1 2 3 4 5 6 7 8 Price: 1 5 8 9 10 17 17 20 Max Value (n=8, recursive) : 22 Max Value (n=8, DP) : 22