Dynamic programming: Fibonacci, knapsack and memoization

In short: Dynamic programming solves problems with overlapping subproblems by storing intermediate results instead of recomputing them; this turns exponential computations into polynomial ones.

In more detail: If a recursive solution solves the same subproblems again and again, you store the results. Two ways: memoization (top-down: recursion + cache) and tabulation (bottom-up: fill a table).

In Depth

Example Fibonacci

fib(n) = fib(n−1) + fib(n−2). Naively recursive, fib(40) takes over 300 million calls (exponential, O(2ⁿ)) because sub-values are computed repeatedly.

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):                 # memoization: O(n)
    return n if n < 2 else fib(n - 1) + fib(n - 2)
 
def fib_tab(n):             # tabulation/bottom-up: O(n), O(1) space
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Deep recursion reaches Python’s recursion limit; bottom-up is then better.

When is DP applicable?

Two properties: optimal substructure (solution composed of optimal sub-solutions) and overlapping subproblems. Procedure: 1) define the state (what describes a subproblem?), 2) formulate the recurrence/transition, 3) base cases, 4) order of computation (table), 5) read out the answer, possibly reconstruct the path. Greedy algorithms are faster but only correct if the greedy choice is provably optimal; DP is safer.

Classics

• Knapsack problem (0/1): items with weight/value, capacity W: dp[i][w] = max(dp[i−1][w], dp[i−1][w−weight_i] + value_i); time O(n·W) (pseudo-polynomial).
• Fewest coins (coin change): dp[x] = 1 + min(dp[x − m]).
• Longest common subsequence (LCS) and edit distance (Levenshtein): basis of diff, spell checking, DNA comparison.
• Shortest paths (Bellman-Ford, Floyd-Warshall).
• Staircase, counting problems, matrix chains, optimal search trees, Viterbi algorithm (speech recognition).

Practice and exam

• Draw the table and fill it by hand: that creates understanding.
• Save space: often the last row/two values suffice.
• Weigh memory/time; O(n·W) can get large.
• Typical errors: wrong base cases, off-by-one, loop order.
• In programming contests, optimisation (routes, cuts, planning), bioinformatics, text comparison.
• Related: recursion, backtracking (tries all paths), greedy, divide and conquer (subproblems do not overlap).

See also: Recursion, Greedy algorithms, Big-O notation