Rod Cutting
Maximize revenue by cutting a rod into pieces with given prices. For each length, try every possible first cut and add the best revenue for the remainder.
- Category
- Dynamic Programming
- Time complexity
- O(n²)
- Space complexity
- O(n)
Pseudocode
for len 1..n
dp[len] = max over cut c of
price[c] + dp[len − c]
Reference implementation
for length in range(1, n+1):
dp[length] = max(price[c] + dp[length-c]
for c in range(1, length+1))