WHAT we want: r(n) = best revenue obtainable from a rod of length n.
HOW to think recursively: the leftmost piece has some length i (where 1≤i≤n). We earn p[i] for it, and the remaining rod of length n−i is a fresh, identical subproblem.
So we try every first-piece length and keep the best:
r(n)=max1≤i≤n(p[i]+r(n−i)),r(0)=0
WHY this is correct: every possible cutting of the rod has some leftmost piece. By looping i over all possible leftmost lengths, we are guaranteed to consider every arrangement. Choosing the max gives the optimum — this is the optimal substructure: an optimal solution to the whole contains optimal solutions to the parts.
def rod_cut(p, n): # p[i] = price of length i, p[0]=0 r = [0]*(n+1) cut = [0]*(n+1) # to reconstruct for j in range(1, n+1): best = float('-inf') for i in range(1, j+1): if p[i] + r[j-i] > best: best = p[i] + r[j-i] cut[j] = i r[j] = best return r[n], cut
Let D(e,f) = minimum worst-case drops with e eggs and f floors.
HOW: drop an egg from some floor x (counting from the bottom of the current range). Two cases, and we must survive the worst:
Egg breaks → threshold is at or below x, in the x−1 floors below. Eggs drop to e−1. Cost: D(e−1,x−1).
Egg survives → threshold is above x, in the f−x floors above. Eggs stay e. Cost: D(e,f−x).
Worst case = the max of the two (adversary picks the worse outcome). We pay 1 for this drop, then choose x to minimize the worst case:
D(e,f)=1+min1≤x≤fmax(D(e−1,x−1),D(e,f−x))
Base cases (WHY they hold):
D(e,0)=0 — zero floors, nothing to test.
D(e,1)=1 — one floor, one drop confirms.
D(1,f)=f — one egg forces linear scan.
def egg_drop(eggs, floors): D = [[0]*(floors+1) for _ in range(eggs+1)] for f in range(1, floors+1): D[1][f] = f for e in range(2, eggs+1): for f in range(1, floors+1): best = float('inf') for x in range(1, f+1): worst = 1 + max(D[e-1][x-1], D[e][f-x]) best = min(best, worst) D[e][f] = best return D[eggs][floors]
WHAT we need: for each node, two answers because the parent's choice depends on whether we are included.
f(v,1) = best weight in v's subtree with v included.
f(v,0) = best weight in v's subtree with v excluded.
HOW to combine children c:
If v is included, no child may be included:
f(v,1)=wv+∑c∈childrenf(c,0)
If v is excluded, each child is free to be included or not — take the best:
f(v,0)=∑c∈childrenmax(f(c,1),f(c,0))
WHY correct: subtrees are disjoint, so their best values simply add. The adjacency constraint only couples a parent with its direct children — exactly what the two states encode.
Answer = max(f(root,1),f(root,0)). Time O(n) (each edge processed once).
def mwis_tree(adj, w, root=0): # adj: adjacency list, w: weights, tree rooted at `root` f0 = [0]*len(w); f1 = [0]*len(w) def dfs(v, parent): f1[v] = w[v]; f0[v] = 0 for c in adj[v]: if c != parent: dfs(c, v) f1[v] += f0[c] f0[v] += max(f0[c], f1[c]) dfs(root, -1) return max(f0[root], f1[root])
adversary forces the worst of {egg breaks, egg survives}
Egg drop base cases
D(e,0)=0, D(e,1)=1, D(1,f)=f
Egg drop with 2 eggs, 10 floors?
4 drops
Why isn't binary search optimal for egg drop?
a broken egg is lost forever; only optimal with unlimited eggs
DP-on-tree MWIS states
f(v,1)=best with v included, f(v,0)=best with v excluded
f(v,1) formula
wv+∑cf(c,0) (children must be excluded)
f(v,0) formula
∑cmax(f(c,1),f(c,0))
DP on tree time complexity
O(n) — each node/edge processed once in DFS
Why does DP work cleanly on trees?
no cycles → each subtree is an independent subproblem
Egg drop dual recurrence (floors from drops)
F(e,d)=F(e−1,d−1)+F(e,d−1)+1
Recall Feynman: explain to a 12-year-old
Rod cutting: You have a long chocolate bar and a price list for pieces. You ask: "What's the best money if I break off a small piece on the left first?" Try every possible first piece, then ask the same question about the leftover bar. The computer remembers the answer for each length so it never re-asks.
Egg drop: You have 2 special eggs and want to find the highest floor you can drop from without breaking. If you guess a floor and it breaks, you must carefully test below it (egg gone!). If it survives, you can try higher. You plan so that even on your unluckiest day you find the floor in as few drops as possible.
DP on trees: Imagine a family tree where each person has a value, but a parent and child can't both be picked (they'd argue!). You start from the youngest kids, figure out the best for each little family, then pass two notes up to each parent: "best if you join" and "best if you sit out." The parent adds up the notes. The top of the tree gives the final best.
Dekho, teeno problems ka core idea ek hi hai: bade problem ko chote identical subproblems me todo, aur har subproblem ka answer ek baar nikaal ke store kar lo — phir dobara mat compute karo. Yahi DP ka asli jaadu hai, exponential se polynomial.
Rod cutting me rod ko pieces me kaatke max paisa kamana hai. Trick: leftmost piece ki length i try karo (1 se n tak), uska price lo, aur baaki n−i length ka rod ek naya same problem ban jata hai — uska best answer pehle se nikla hua hai. Formula: r(n)=max(p[i]+r(n−i)). Bas saare i try karke max le lo.
Egg drop thoda dimaag-ghumaau hai. e ande aur f floors hain, worst case me minimum drops chahiye. Kisi floor x se drop karo: agar anda toot gaya to neeche x−1 floors me threshold hai aur ek anda kam — D(e−1,x−1). Agar bach gaya to upar f−x floors me, ande wahi — D(e,f−x). Adversary worst case dega isliye in dono ka max lo, aur phir best x chunne ke liye min. Yaad rakho: binary search yahan optimal nahi, kyunki ek toota anda hamesha ke liye gaya — info lost!
DP on trees sabse clean hai. Tree me cycle nahi hota, isliye har subtree independent subproblem hai. DFS se neeche (leaves) se shuru karo. Har node do answer bhejta hai parent ko: "agar main include hua" (f(v,1)=wv+∑f(c,0), children exclude) aur "agar main exclude hua" (f(v,0)=∑max(f(c,1),f(c,0))). Bas O(n) time. Greedy yahan fail hoti hai — heavy node uthane se uske padosi block ho jaate hain. Mantra yaad rakho: "Rod LEFT, Egg WORST, Tree TWO notes."
