Visual walkthrough — DP problems — rod cutting, egg drop, DP on trees

---

Step 1 — What is a rod, and what is "revenue"?

WHAT. A rod is just a straight bar of whole-number length. Length $n$ means it is $n$ units long. We are handed a price list $p$: the number $p[i]$ is how many coins a piece of length $i$ sells for. We are allowed to chop the rod at whole-number marks and sell each piece.

WHY. Before any formula, we must agree on the thing we are counting. Here it is revenue — total coins from all the pieces we produce. The whole game is: choose where to cut so the coins add up to the most.

PICTURE. Look at the rod below (length 4) and the price ruler underneath it. Each tick is one cuttable position. The amber numbers are the prices $p[\mathrm{1..4}]$.

---

Step 2 — The single most important choice: the leftmost piece

WHAT. Instead of imagining all cuts at once (there are exponentially many patterns), we make one decision only: how long is the first piece, measured from the left end? Call that length $i$. Then we sell that piece for $p[i]$ and forget it forever — what's left is a shorter rod of length $n-i$.

WHY. This is the trick that turns a giant problem into a tiny one plus a smaller copy of itself. Every possible way to cut the rod has some leftmost piece. So if we consider every possible value of $i$, we have secretly considered every cutting pattern — without listing them.

PICTURE. The red bracket marks the leftmost piece of length $i$. The cyan bracket is the leftover rod of length $n-i$. Notice the leftover is just... another rod. Same problem, smaller.

---

Step 3 — Naming the answer: the function $r(n)$

WHAT. Define $r(n)$ = the best revenue you can possibly get from a rod of length $n$. Not any revenue — the maximum.

WHY. We need a name for "the answer to a rod of length $n$" so that when the leftover rod ($n-i$) appears, we can refer to its best answer as $r(n-i)$ — the same function, called on a smaller input. This is what lets the problem close in on itself.

PICTURE. The box labelled $r(n)$ is a machine: feed it a length, out comes the best coins. Feed it a smaller length and it happily answers again.

---

Step 4 — Assembling the recurrence, term by term

WHAT. For a fixed first-piece length $i$, our total is: coins for the first piece, $p[i]$, plus the best coins from the leftover, $r(n-i)$. We don't know the best $i$ yet, so we try every $i$ from $1$ to $n$ and keep the largest sum:

$$r(n)=\underset{1\le i\le n}{\max }(\underset{\begin{array}{c}\text{coins for the}\\ \text{leftmost piece of length }i\end{array}}{\underbrace{p[i]}}+\underset{\begin{array}{c}\text{best coins from the}\\ \text{leftover rod of length }n-i\end{array}}{\underbrace{r(n-i)}})$$

Reading the pieces of this formula:

• $\underset{1\le i\le n}{\max }$ ::: "try every leftmost length $i$ from $1$ up to $n$, and take the winner."
• $p[i]$ ::: guaranteed coins for that first piece — a known number from the price list.
• $r(n-i)$ ::: the best we can do on everything after that piece — the same machine on a smaller rod.
• The $+$ ::: the two are disjoint (piece and leftover never overlap), so their coins simply add.

WHY the $\max$. The adversary here is our own indecision — we want the biggest total, so among all first-cut choices we pick the one that maximizes the sum. Because every cutting pattern is captured by some $i$, the max over $i$ is the true best.

PICTURE. Each row is one choice of $i$; the bar's total length is $p[i]+r(n-i)$. The tallest (amber) bar is the winner the $\max$ selects.

---

Step 5 — Why naive recursion is a disaster (and the fix)

WHAT. If we literally code $r(n)$ as a function calling itself, it recomputes the same smaller rods over and over. $r(4)$ needs $r(3),r(2),r(1)$; but $r(3)$ also needs $r(2),r(1)$; and $r(2)$ needs $r(1)$ again. The same node explodes across the call tree.

WHY it's fatal. The number of repeated calls grows exponentially ($\sim 2^n$). Yet there are only $n+1$ genuinely different questions: $r(0),r(1),\dots ,r(n)$. We are re-answering a handful of questions billions of times.

THE FIX. Store each answer the first time we compute it. This is memoization (top-down) or a filled table (bottom-up). Now every $r(j)$ is computed once.

PICTURE. Left: the exploding recursion tree, with duplicate nodes glowing red. Right: the same work collapsed into a single row of $n+1$ boxes, each filled once.

---

Step 6 — Filling the table bottom-up

WHAT. Instead of recursing downward, we build $r$ upward: compute $r[1]$, then $r[2]$, ... each using answers already sitting in the array. To reconstruct the cuts, we also store, in $\text{cut}[j]$, the winning leftmost length $i$.

$$r[j]=\underset{1\le i\le j}{\max }(p[i]+r[j-i])$$

• $r[j]$ ::: the box we are currently filling (the best revenue for length $j$).
• $r[j-i]$ ::: a box already filled earlier (a shorter rod), so it's just a lookup — no recursion.
• $\text{cut}[j]$ ::: remembers which $i$ won, so we can rebuild the actual pieces afterward.

WHY it works left-to-right. When we fill box $j$, every box it needs ($0$ up to $j-1$) is already done. No box waits on a box to its right.

PICTURE. The table for $p=[\_,1,5,8,9]$, $n=4$. Arrows show box $j=4$ pulling from earlier boxes $r[3],r[2],r[1],r[0]$ as $i$ ranges over $1,2,3,4$.

---

Step 7 — Every edge case, so nothing surprises you

WHAT. We check the boundary and degenerate inputs so the reader never hits an unshown scenario:

• $n=0$ (empty rod). $r(0)=0$ by the base case. The $\max$ loop never runs (no valid $i$). ✔
• $n=1$ (shortest real rod). Only $i=1$ is allowed: $r(1)=p[1]+r(0)=p[1]$. ✔
• "Don't cut at all" is included. Choosing $i=n$ gives $p[n]+r(0)=p[n]$ — selling the whole rod uncut. It's just one of the candidates the $\max$ compares, so no special case is needed. ✔
• A price that's "too cheap." If $p[i]$ is small, the term $p[i]+r[j-i]$ simply loses the $\max$; nothing breaks. Even $p[i]=0$ is fine.

WHY show these. DP correctness lives or dies at the boundary. If $r(0)$ were wrong, every later box built on it would be poisoned. The "sell whole" case being automatic is what proves we never need an extra branch for "zero cuts."

PICTURE. Three mini-rods: length 0 (nothing, value 0), length 1 (one option), and the uncut length-$n$ rod shown as the single-piece candidate feeding into the same $\max$.

Recall Check yourself on the edges

What is $r(0)$ and why? ::: $0$ — an empty rod has no pieces to sell; it is the base case every other value builds on. How does the recurrence handle "make no cuts"? ::: Via $i=n$, giving $p[n]+r(0)=p[n]$; it is one candidate inside the $\max$, so no special branch is required. Why must the table be filled from small $j$ to large $j$? ::: Because $r[j]$ reads $r[j-i]$ for smaller indices — those must already be computed.

---

The one-picture summary

Everything on this page compressed into one figure: the leftmost-piece choice (Step 2) becomes the recurrence (Step 4), the recurrence fills a table left-to-right (Step 6), and reconstruction walks the $\text{cut}$ pointers back into actual pieces.

Recall Feynman retelling — say it in plain words

Imagine you're selling a bar and someone hands you a price list per length. You don't try every crazy way to chop it — that's a nightmare. Instead you ask one small question: how long is the very first piece I break off? You try each possible first length, pocket its price, then hand the remaining bar back to yourself and ask the exact same question — but now the bar is shorter, so it's an easier version of the same puzzle. The answer to "best coins for a bar of length $L$" is called $r(L)$, and it equals: for each first-length $i$, add the price $p[i]$ to the best you can do on the leftover $r(L-i)$, and keep the biggest. The base case is $r(0)=0$: an empty bar is worth nothing. The only clever bit is don't re-solve the same shorter bar twice — write each answer in a little box the first time, then just read the box. That's the whole idea: recursion with a notepad, filling boxes from length $1$ upward, and following breadcrumbs (which first-cut won) to rebuild the actual pieces at the end.

---

Recall Connections

This walkthrough is the visual companion to the Dynamic Programming paradigm and leans directly on Recursion and Memoization. Compare its "try-every-first-choice" flavour with Greedy Algorithms (which commits to one choice), with Binary Search (used to speed the egg-drop cousin), with Tree Traversal (DFS) (the engine of DP-on-trees), and with the Knapsack Problem (the closest structural sibling of rod cutting). Full context: the parent topic note.