Rod Cutting

Richard Bellman, 1954

Richard Bellman’s dynamic programming formulation (1950s) turns rod cutting into a shortest-path-in-disguise: dp[ℓ] is the best revenue for length ℓ, considering every first cut that leaves a left piece with catalog price and a right remainder solved recursively. The animation mirrors a textbook double loop over length and cut position, highlighting the active dp cell in gold and freezing the optimal full-length answer in coral.