Dynamic Programming: Complete Beginner's Guide For students.

Dynamic programming (DP) solves a problem by breaking it into overlapping subproblems, solving each one once, and storing the answers for reuse. The classic victim is naive recursive Fibonacci: computing F(40) recomputes F(20) millions of times. DP computes each value once — bottom-up in a table or top-down with memoisation — turning exponential time into linear.

DP matters because it cracks problems that look impossibly hard: shortest routes, DNA alignment, spell checkers, and resource allocation all run on DP. It is also the most feared interview topic, because its solutions look like magic until you see the recurrence underneath.

Key Concepts

• Overlapping subproblems: the same smaller problem recurs many times (F(38) is computed twice inside F(40)).
• Optimal substructure: the optimal answer is built from optimal answers to subproblems.
• Memoisation (top-down): keep recursion but cache each result; every subproblem solved once.
• Tabulation (bottom-up): fill a table iteratively from the smallest subproblem upward.
• State: the parameters defining a subproblem, e.g., dp[i] = F(i), or dp[i][w] for knapsack with capacity w.
• Recurrence: the formula linking a state to smaller states, e.g., F(n) = F(n−1) + F(n−2).
• 0/1 knapsack: dp[i][w] = max(dp[i−1][w], dp[i−1][w − wt[i]] + val[i]) — take the item or leave it.

Formulas

• Fibonacci: F(n) = F(n−1) + F(n−2), F(0) = 0, F(1) = 1. Naive: O(1.618^n); DP: O(n) time, O(1) space keeping two values.
• 0/1 knapsack: dp[i][w] = max(dp[i−1][w], dp[i−1][w−wt[i]] + val[i]). Time O(n·W), space reducible to O(W).
• Longest common subsequence: match → dp[i−1][j−1] + 1, else max(dp[i−1][j], dp[i][j−1]). Time O(m·n).
• Edit distance: dp[i][j] = min(insert, delete, replace) + cost over string prefixes; O(m·n).
• Coin change (min coins): dp[x] = 1 + min(dp[x − c]) over denominations c ≤ x; dp[0] = 0.

Worked Example

F(6) by tabulation: table[0] = 0, table[1] = 1; table[2] = 1 + 0 = 1; table[3] = 1 + 1 = 2; table[4] = 2 + 1 = 3; table[5] = 3 + 2 = 5; table[6] = 5 + 3 = 8. Answer 8 in 6 additions — naive recursion needs 25 calls for the same answer. Knapsack: capacity 5, items A(2,3), B(3,4), C(4,5) as (weight, value). Row A: [0,0,3,3,3,3]. Row B: w=2 → 3 (B too heavy); w=3 → max(3, 0+4) = 4; w=4 → max(3, 4) = 4; w=5 → max(3, 3+4) = 7. Row C (weight 4): w=4 → max(4, 5) = 5; w=5 → max(7, 5) = 7. Final answer 7 — items A + B (weight 5, value 7). Each cell reused earlier cells; nothing recomputed.

Common Misconceptions

• "DP is a specific algorithm." Wrong. It is a technique — structuring solutions around recurrences and stored subproblems — applied to hundreds of problems.
• "Memoisation and tabulation differ." They are two implementations of one idea: top-down caching versus bottom-up tables. Same recurrence, same complexity.
• "DP always beats greedy." Not in simplicity. Where the greedy-choice property holds, greedy is simpler and often faster; DP is the fallback when greed fails.

Real-World Applications

• Bioinformatics: DNA sequence alignment is DP over two strings.
• Spell checkers / diff tools: edit distance finds the closest word or file diff.
• Operations research: knapsack-style DP allocates budgets and cargo space.
• Speech recognition: the Viterbi algorithm (a DP) decodes likely word sequences.

Dynamic programming is organised laziness: never solve the same subproblem twice. Find the recurrence, define the states, fill the table — and exponential monsters shrink into clean polynomial solutions.