rod-cutting

Rod-Cutting Problem

Definition

Given a rod of length $n$, a rod of length $i$ is sold at price $p_i$, find maximum revenue $r_n$.

$$r_n=\max \{p_i+r_{n-i}:1\le i\le n\}$$

Solution

A trivial top-down recursive approach takes exponential time, as it explicitly considers each of the subproblems over and over again.

Dynamic programming solves this problem in $O(n^2)$ time.

Store the optimal revenue for each length, also store the length of the first optimal cut to reconstruct the solution.