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:

1. Create DP table of size = n +1
2. Set table[0] = 0
3. Iterate i from 1 to n
   1. Set max = INFINITY
   2. Iterate j from 0 to 1
      1. Set max = Max {max, price [i] + table[i-j-1] }
      2. Set table[i] = max
4. 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

Video

Video