code/dynamic_programming/src/rod_cutting/README.md
Given a rod of length n units and an array of prices p<sub>i</sub> for rods of length i = 1, 2, . . . ,n. Determine the maximum revenue r <sub>n</sub> obtainable by cutting the rod and selling the pieces.
Let the table of prices be -
| length (i) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| price (p<sub>i</sub>) | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
For a rod of length n = 4
Image credits: (CS Indiana)
Image credits: (Medium: Pratik Anand)
Maximum revenue is obtained by cutting the rod into two pieces each of length 2. Thus, maximum revenue obtained is 10.
This problem satisfies both properties of Dynamic programming and can be solved by the following recurrence relation.
Time complexity : O(n^2)
Space complexity : O(n)