DP problems — rod cutting, egg drop, DP on trees: Question bank

Definition Symbols and recurrences used on this page

Before you tackle the traps, here is every symbol and formula, in plain words, in one place.

Rod cutting. A rod has integer length $n$ . The ==price array $p [1.. n]$ == gives $p [i]$ = the money you get for selling one piece of length $i$ (index 0 is unused, and we set $p [0] = 0$ ). Define == $r (n)$ == = the best total revenue obtainable from a rod of length $n$ . Its recurrence, trying every possible leftmost piece length $i$ : $r (n) = max_{1 \leq i \leq n} (p [i] + r (n - i)), r (0) = 0.$ The bottom-up array version writes $r [j]$ for $r (j)$ , so $r [j - i]$ just means "the best revenue for the remaining rod of length $j - i$ ".

Egg drop. With == $e$ eggs and $f$ floors, define $D (e, f)$ == = the minimum number of drops that guarantees finding the threshold floor in the worst case. You drop from floor $x$ ; it either breaks (threshold at or below $x$ , $x - 1$ floors left, one fewer egg) or survives ( $f - x$ floors above, same eggs): $D (e, f) = 1 + min_{1 \leq x \leq f} max (D (e - 1, x - 1), D (e, f - x)) .$ Base cases: $D (e, 0) = 0$ , $D (e, 1) = 1$ , $D (1, f) = f$ . The dual quantity == $F (e, d)$ == = the maximum number of floors you can fully resolve with $e$ eggs and $d$ drops: $F (e, d) = F (e - 1, d - 1) + F (e, d - 1) + 1, F (e, 0) = F (0, d) = 0.$

DP on trees — MWIS. ==MWIS = Maximum Weighted Independent Set==: each node $v$ has a ==weight $w_{v}$ ==, and we pick a set of nodes with no two adjacent so the total weight is largest. Let $c$ range over the ==children of $v$ == (written $c \in ch (v)$ ). Two states: $f (v, 1) = w_{v} + \sum_{c \in ch (v)} f (c, 0), f (v, 0) = \sum_{c \in ch (v)} max (f (c, 1), f (c, 0)) .$ Here $f (v, 1)$ = best subtree weight with $v$ included, $f (v, 0)$ = best with $v$ excluded; the answer is $max (f (root, 1), f (root, 0))$ .

True or false — justify

Recall Reveal all

Rod cutting requires that the cuts be made at integer positions. ::: True — the price array $p [1.. n]$ only defines values for integer lengths, so a "piece of length 2.5" has no defined price; the whole model lives on integers. In rod cutting, looping the leftmost piece over $1.. n$ misses some cuttings because it never fixes the rightmost piece. ::: False — every cutting has exactly one leftmost piece, so ranging over all leftmost lengths and recursing on the rest already covers every arrangement; fixing the rightmost would be a redundant second way to say the same thing. Egg drop's answer $D (e, f)$ can never exceed $f$ . ::: True — the one-egg strategy (scan floor by floor) always works and costs at most $f$ drops, so more eggs can only help; $D (e, f) \leq D (1, f) = f$ . With unlimited eggs, egg drop collapses to binary search and the answer is $⌈ lo g_{2} (f + 1)⌉$ . ::: True — with eggs to spare a break is never catastrophic, so each drop can split the remaining candidate floors plus the "no floor" outcome in half; $k$ drops distinguish at most $2^{k}$ outcomes, and there are $f + 1$ possible thresholds (floors $1.. f$ or "never breaks"), so you need $2^{k} \geq f + 1$ , i.e. $k = ⌈ lo g_{2} (f + 1)⌉$ . In DP on trees, the two states $f (v, 0)$ and $f (v, 1)$ are needed because a node's optimal contribution depends on a choice its parent hasn't made yet. ::: True — the parent must know "what's the best you offer if I take you" versus "if I don't", so the child publishes both and lets the parent pick. MWIS on a tree can be solved greedily by always picking leaves first. ::: False in general — picking leaves is a heuristic that can lose; the two-state DP is what guarantees optimality by comparing include-vs-exclude for every subtree. The rod-cutting recurrence is essentially unbounded knapsack in disguise. ::: True — each length $i$ is an item of "weight" $i$ and value $p [i]$ reusable any number of times, capacity $n$ ; see Knapsack Problem. Memoizing the top-down rod-cutting recursion changes the answer it returns. ::: False — memoization only removes recomputation; the value is identical to the plain recursion, it just runs in $O (n^{2})$ instead of exponential time.

Spot the error

Recall Reveal all

"Rod cutting base case: $r (1) = 0$ because a length-1 rod can't be cut." ::: Error — you don't have to cut. $r (1) = p [1]$ : the "zero cuts" option (sell the whole piece) is always allowed, so $r (1)$ equals the price of length 1, not 0. "Egg drop: when the egg breaks at floor $x$ , the sub-problem is $D (e - 1, x)$ floors below." ::: Error — a break means the threshold is at or below $x$ , leaving $x - 1$ floors to test (floor $x$ itself is now known to be a breaking floor), so it's $D (e - 1, x - 1)$ . "Egg drop: take the min of the break case and survive case, since we hope for the better outcome." ::: Error — you don't control which happens; the adversary (worst case) does, so you must take the max of the two, then minimize over $x$ . "MWIS: $f (v, 1) = w_{v} + \sum_{c \in ch (v)} max (f (c, 0), f (c, 1))$ ." ::: Error — if $v$ is included, no child may be included, so each child is forced to state 0: $f (v, 1) = w_{v} + \sum_{c \in ch (v)} f (c, 0)$ . The $max$ only appears in $f (v, 0)$ . "MWIS: the answer is $f (root, 1)$ because including the root captures the most weight." ::: Error — the root might be better left out; the answer is $max (f (root, 1), f (root, 0))$ . "DP on a tree must process nodes root-first (pre-order) so the root's answer is ready." ::: Error — a node needs its children's answers first, so you process leaves-up (post-order / DFS return); the root is computed last, not first. "Rod cutting is $O (n)$ because you fill one array of size $n$ ." ::: Error — filling entry $r [j]$ costs an inner loop of up to $j$ trials, so the total is $O (n^{2})$ , not $O (n)$ .

Why questions

Recall Reveal all

Why does DP beat brute force for these three problems specifically? ::: Because the same subproblem (shorter rod / fewer eggs-floors / same subtree) recurs exponentially many times in the naive tree; solving each once and caching turns exponential into polynomial. Why is the tree case $O (n)$ while rod cutting is $O (n^{2})$ ? ::: In a tree each edge is touched exactly once (each child feeds its parent once), whereas rod cutting re-scans all shorter lengths at every $j$ , giving a quadratic double loop. Why does egg drop use $min$ over $x$ but $max$ over outcomes? ::: You choose the drop floor $x$ to your advantage (min), but you cannot choose whether it breaks — nature/adversary picks the worse branch (max). Why can't we reuse the rod-cutting item-once logic here — why is it unbounded? ::: A length- $i$ piece can be cut out repeatedly (a length-6 rod could be three length-2 pieces), so each "item" is reusable, unlike 0/1 knapsack; that's why the recurrence recurses on $r [j - i]$ (same rod again), not $r [j - i]$ with item $i$ removed. Why does the "dual" egg-drop view $F (e, d) = F (e - 1, d - 1) + F (e, d - 1) + 1$ give the same answer faster? ::: It flips the question to "with $d$ drops and $e$ eggs, how many floors can I clear?"; the drop splits floors into the break-branch ( $F (e - 1, d - 1)$ ), the survive-branch ( $F (e, d - 1)$ ), plus the current floor. How do you recover $D (e, f)$ from the dual $F (e, d)$ ? ::: Since $F$ is strictly increasing in $d$ , "the fewest drops that clear $\geq f$ floors" equals "the smallest $d$ with $F (e, d) \geq f$ "; scan $d = 1, 2, 3, \dots$ and stop at the first that reaches $f$ — that $d$ is $D (e, f)$ , because $F (e, D (e, f)) \geq f$ but $F (e, D (e, f) - 1) < f$ . Why do subtrees add cleanly in MWIS but "just adding" fails across a parent–child edge? ::: Sibling subtrees are disjoint (no shared nodes, no adjacency between them) so their optima add; a parent and child are adjacent, so they can't both be picked — that single constraint is exactly what the two states manage. Why is greedy correct for some problems but not MWIS? ::: Greedy Algorithms work only when a local best is guaranteed globally optimal (matroid-like structure); MWIS lacks it because a heavy node blocks neighbors whose combined weight can exceed it.

Edge cases

Recall Reveal all

Rod cutting with $n = 0$ : what is $r (0)$ ? ::: $r (0) = 0$ — an empty rod yields no revenue; this base case anchors every longer recurrence. Rod cutting where selling whole always wins — does the algorithm still cut? ::: No — trying leftmost piece $i = n$ leaves $r (0) = 0$ , giving $p [n]$ ; if that's the max, cut[n]=n records a single (trivial) piece, i.e. no real cut. Egg drop with a single egg, $e = 1$ , arbitrary $f$ : what is $D (1, f)$ ? ::: $D (1, f) = f$ — one egg forces a bottom-up linear scan (a break is permanent, so you can never risk skipping a floor), costing up to $f$ drops in the worst case. Egg drop with $e = 0$ eggs and $f \geq 1$ floors: what should $D (0, f)$ be? ::: Undefined / impossible ( $\infty$ ) — with no eggs you can never test a floor, so no finite strategy guarantees finding $T$ ; only $D (e, 0) = 0$ is a safe zero. Egg drop with $f = 0$ floors: why is $D (e, 0) = 0$ for every $e$ ? ::: There is nothing to identify — zero floors means the threshold question is already resolved, so zero drops are needed regardless of egg count. Egg drop, exactly 1 floor: why is $D (e, 1) = 1$ and not 0? ::: You still must confirm whether that single floor is a breaking floor, which requires one drop; knowing the building exists isn't the same as knowing the threshold. MWIS on an empty tree (zero nodes): what's the answer? ::: $0$ — the empty set $\emptyset$ is a valid independent set with total weight 0; the DFS never runs, so no state is set and the base return is 0. MWIS on a single-node tree: what's the answer? ::: $max (f (v, 0), f (v, 1)) = max (0, w_{v}) = w_{v}$ if $w_{v} > 0$ ; a lone node has no neighbor to block it. MWIS with all-negative weights: does the DP still work? ::: Yes — the exclude state $f (v, 0)$ can leave every node out (contributing 0), so the answer is $\geq 0$ ; the "empty set" is always a legal independent set. A path graph (a degenerate "tree" that is one line): does tree-MWIS still apply? ::: Yes — root it at one end and DFS; the recurrence reduces to the classic 1-D house-robber DP, since each node has at most one child. Star graph, centre weight 10, four leaves weight 4: what does the DP output and why does greedy fail? ::: DP outputs $16$ (all four leaves), because excluding the centre frees every leaf; greedy grabs the centre (10) first, blocks all leaves, and loses — the two-state comparison catches this globally.