Rod Cutting

Problem. A rod of length $n$ can be cut into integer pieces. A piece of length $i$ sells for $p_i$. Maximise the total revenue.

The DP — $O(n^2)$

$dp[len]={\max }_{1\le i\le len}(p_i+dp[len-i]).$

long long rodCutting(int n, const vector<long long>& p) {   // p[1..n]
    vector<long long> dp(n + 1, 0);
    for (int len = 1; len <= n; len++)
        for (int i = 1; i <= len; i++)
            dp[len] = max(dp[len], p[i] + dp[len - i]);
    return dp[n];
}

This is unbounded knapsack in disguise: items are the piece lengths, weights are the lengths, values are the prices, and the capacity is $n$. Written that way it is $O(n\cdot k)$ for $k$ distinct lengths.

for (int i = 1; i <= k; i++)
    for (int len = length[i]; len <= n; len++)              // UPWARD: unlimited copies
        dp[len] = max(dp[len], dp[len - length[i]] + price[i]);

Reconstruction

vector<int> cut(n + 1, 0);                                  // first piece length
// during the DP: if improved, cut[len] = i;
int len = n;
while (len > 0) { pieces.push_back(cut[len]); len -= cut[len]; }

Variants

Variant	Change
Rod cutting	unbounded knapsack
Cost per cut $c$	$dp[len]=\max (p_{len},{\max }_i(dp[i]+dp[len-i]-c))$
At most $k$ pieces	add a dimension, $O(n^{2}k)$
Each length usable once	0/1 knapsack — weight loop downward
Maximise the product of piece lengths	see below
Cutting sticks (given cut positions)	interval DP, $O(m^3)$
2D cutting stock	much harder; NP-hard

Maximum product of piece lengths

“Cut $n$ into positive integers maximising their product.”

The answer is to use as many 3s as possible, with the remainder handled specially:

$n\mathrm{mod}3$	Pieces
0	all 3s
1	one 4 (or two 2s), rest 3s — never a 1
2	one 2, rest 3s

Why: $3^{1/3}>2^{1/2}>4^{1/4}>\dots$, so 3 is the most “efficient” piece per unit length; and $1$ is always wasteful ($1\times x<1+x$ combined). The continuous optimum is $e\approx 2.718$, and 3 is the nearest integer.

long long maxProduct(int n) {
    if (n <= 3) return n - 1;                               // special small cases
    if (n % 3 == 0) return ipow(3, n / 3);
    if (n % 3 == 1) return 4 * ipow(3, (n - 4) / 3);
    return 2 * ipow(3, (n - 2) / 3);
}

Cutting sticks — the interval-DP cousin

“A stick of length $L$ must be cut at $m$ given positions. Each cut costs the length of the piece being cut. Minimise the total cost.”

$dp[i][j]={\min }_{i<k<j}(dp[i][k]+dp[k][j])+(x_j-x_i),$

with the cut positions (plus 0 and $L$) as the endpoints. $O(m^3)$, or $O(m^2)$ with Knuth optimization since the cost satisfies the quadrangle inequality.

This is the same recurrence as matrix chain multiplication and merging stones — a good illustration that interval DP is one pattern wearing several costumes.

Why it is worth knowing

Rod cutting is usually the first DP anyone meets after Fibonacci, and it teaches two things:

1. Recognising a known problem in disguise — it is unbounded knapsack, and seeing that immediately gives the $O(nk)$ form and all its variants.
2. The loop direction encodes the semantics — upward for unlimited copies, downward for one each. Same three lines, different problem.

See also: Knapsack · Interval DP · Matrix Chain Multiplication