212. Rod Cutting Problem

Given a rod of length n and a price list where price[i] is the price of a piece of length i (1-indexed, i from 1 to n), find the maximum total profit obtainable by cutting the rod into pieces (any number of pieces, including zero cuts) and selling each piece.

Input: The first line contains an integer n, the rod length. The second line contains n space-separated integers, price[1..n], the price of a piece of each length from 1 to n. Output: Print a single integer - the maximum total profit obtainable by cutting the rod.

1 <= n <= 1000

'Zero cuts' (selling the rod whole) is always one of the options implicitly considered, since trying i=len as the 'first piece' directly gives price[len] + dp[0] = price[len] - the DP naturally includes this case without special-casing.

Cut a rod into pieces to maximize the total selling profit, given a price list per piece length. Brute force: Try every possible way of partitioning the rod into pieces directly (all possible cut-point combinations) - this is exponential (2^(n-1) possible cut patterns), impractical for large n. Optimised: The DP recognizes that the best profit for a rod of length `len` only depends on the best profits for SHORTER rods (after cutting off some first piece) - building the table bottom-up computes each shorter rod's best profit exactly once, reused by every longer rod that needs it.

For a rod of length n, recursively try every possible first-cut length i from 1 to n, add price[i] to the best achievable profit from optimally cutting up the remaining rod of length n-i, and take the maximum over all choices of i. This directly mirrors the problem's definition of trying all ways to cut the rod, but the same remaining-length subproblems are solved repeatedly from different cut sequences, causing exponential growth. Time: O(2^n) Space: O(n)

Keep the same recursive structure - try every first-cut length and recurse on the remainder - but cache the best profit computed for each remaining rod length the first time it's needed, keyed by length, so future calls for that same length are answered instantly from the cache. Since there are only n distinct subproblems (one per possible remaining length), this collapses the exponential brute force down to O(n) distinct computations, each doing O(n) work to try all cut choices. Time: O(n^2) Space: O(n)

Build a 1D array dp where dp[len] is filled iteratively for len = 1 up to n, computing dp[len] = max over cut sizes i from 1 to len of price[i] + dp[len-i], relying only on already-computed smaller lengths. This produces the identical result as the memoized recursion but iteratively from the bottom up, avoiding recursion call overhead and any risk of stack growth, and keeps the computation cache-friendly since it always scans previously filled entries in order. Time: O(n^2) Space: O(n)

1. dp[len] = maximum profit obtainable from a rod of length len. 2. dp[len] = max over every piece length i from 1 to len of (price[i] + dp[len-i]) - trying every possible FIRST piece to cut off, then recursing on the remainder. 3. dp[0]=0 as the base case (nothing left to cut).

Time: O(n²) - for each of the n rod lengths, trying every possible first-piece length. Space: O(n), for the dp array.

Test n = 1, a price list where cutting never helps (e.g. price directly proportional to length, so zero cuts is optimal), and n at the upper bound of 1000.

Be ready to connect this directly to unbounded knapsack - each piece length can be used any number of times (since you can cut the SAME length multiple times), making this structurally similar to that problem's 'reuse within the same computation' pattern.