# 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. [[dp|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.