Top-down is natural but risks stack overflow. Bottom-up avoids recursion and enables space optimization. Greedy only works with proof.
TOP-DOWN vs BOTTOM-UP vs GREEDY
────────────────────────────────
TOP-DOWN (memoized recursion):
@cache
def dp(state):
if base_case: return ...
return combine(dp(sub1), dp(sub2))
→ Natural when recurrence is clear
→ Only computes needed states
→ Risk: stack overflow on deep recursion
BOTTOM-UP (tabulation):
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = combine(dp[i-1], dp[i-2], ...)
→ No recursion overhead
→ Can optimize space (rolling array)
→ Must determine fill order
GREEDY (local optimal = global optimal):
sort by some criterion
for item in items:
if can_take(item): take it
→ Only works with greedy-choice property
→ Prove correctness by exchange argument
→ Examples: activity selection, Huffman, coin change (specific denoms)
DECISION:
Overlapping subproblems? → DP (top-down or bottom-up)
Need all states anyway? → bottom-up (often faster)
Sparse state space? → top-down (skip unused)
Greedy-choice property? → greedy (prove first!)
"Min cost / max value"? → DP unless greedy proven