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

3.7.14 · Coding › Algorithm Paradigms

1. Rod Cutting

Recurrence scratch se derive karna

KIYA CHAHIYE: $r(n)$ = length $n$ ki rod se milne wala best revenue.

RECURSIVE SOCHNE KA TARIKA: sabse left wale piece ki koi length $i$ hogi (jahan $1\le i\le n$). Hum usse $p[i]$ kamaate hain, aur bacha hua $n-i$ length ka rod ek fresh, same subproblem hai.

Toh hum har first-piece length try karte hain aur best rakhte hain:

$r(n)={\max }_{1\le i\le n}(p[i]+r(n-i)),r(0)=0$

YEH KYUN SAHI HAI: rod ki har possible cutting mein koi na koi sabse left wala piece hoga. $i$ ko saare possible leftmost lengths pe loop karke, hum guaranteed hai ki har arrangement consider ki gayi. Max lena optimum deta hai — yeh hai optimal substructure: poore ka optimal solution parts ke optimal solutions contain karta hai.

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

2. Egg Drop

Recurrence derive karna

$D(e,f)$ = $e$ eggs aur $f$ floors ke saath minimum worst-case drops.

TARIKA: kisi floor $x$ se egg drop karo (current range ke neeche se count karte hue). Do cases, aur humein worst mein survive karna hai:

• Egg breaks → threshold $x$ pe ya neeche hai, neeche ke $x-1$ floors mein. Eggs $e-1$ ho jaate hain. Cost: $D(e-1,x-1)$.
• Egg survives → threshold $x$ se upar hai, upar ke $f-x$ floors mein. Eggs $e$ rehte hain. Cost: $D(e,f-x)$.

Worst case = dono ka max (adversary bura outcome choose karta hai). Is drop ke liye 1 pay karte hain, phir worst case minimize karne ke liye $x$ choose karte hain:

$D(e,f)=1+{\min }_{1\le x\le f}\max (D(e-1,x-1),D(e,f-x))$

Base cases (WHY yeh hold karte hain):

• $D(e,0)=0$ — zero floors, kuch test nahi karna.
• $D(e,1)=1$ — ek floor, ek drop confirm karta hai.
• $D(1,f)=f$ — ek egg linear scan force karta hai.

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]

3. DP on Trees

States derive karna

KIYA CHAHIYE: har node ke liye do answers kyunki parent ki choice depend karti hai ki hum include hain ya nahi.

• $f(v,1)$ = $v$ ke subtree mein best weight $v$ include karte hue.
• $f(v,0)$ = $v$ ke subtree mein best weight $v$ exclude karte hue.

HOW children $c$ ko combine karo:

• Agar $v$ included hai, koi bhi child included nahi ho sakta: $f(v,1)=w_v+{\sum }_{c\in \text{children}}f(c,0)$
• Agar $v$ excluded hai, har child include ho sakta hai ya nahi — best lo: $f(v,0)={\sum }_{c\in \text{children}}\max (f(c,1),f(c,0))$

WHY SAHI HAI: subtrees disjoint hain, isliye unke best values simply add ho jaate hain. Adjacency constraint sirf parent ko uske direct children se couple karti hai — exactly yahi do states encode karti hain.

Answer = $\max (f(\text{root},1),f(\text{root},0))$. Time $O(n)$ (har edge ek baar process hoti hai).

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])

Flashcards

Connections

• Dynamic Programming — optimal substructure + overlapping subproblems
• Recursion and Memoization — teeno ke top-down version
• Greedy Algorithms — contrast: greedy MWIS & egg drop mein fail hota hai
• Binary Search — egg-drop ke ${\min }_x$ ko speed up karta hai aur clarify karta hai ki akela kyun fail hota hai
• Tree Traversal (DFS) — post-order tree DP ka engine hai
• Knapsack Problem — rod cutting unbounded knapsack hai jisme length=weight=price-index

Concept Map