CLRS BOTTOM-UP-CUT-ROD (type it)

Answer

BOTTOM-UP-CUT-ROD(p, n) let r[0..n] be new array r[0] = 0 for j = 1 to n q = -∞ for i = 1 to j q = max(q, p[i] + r[j - i]) r[j] = q return r[n]

The outer loop fixes the rod length j; the inner loop tries every first-cut i and reuses the already-computed r[j-i]. Doubly nested → Θ(n²).