Dynamic Programming

Also Known As

TL;DR

Explanation

Dynamic programming applies when a problem has optimal substructure (optimal solution built from optimal subproblems) and overlapping subproblems (same subproblem solved multiple times). Two approaches: top-down memoisation (recursive with a cache) and bottom-up tabulation (iterative, fill a table). Classic examples: Fibonacci, longest common subsequence, knapsack problem. In web development, DP appears in query result caching, diff algorithms, and compiler optimisations.

Diagram

flowchart TD
    subgraph Naive Fibonacci - Exponential
        F5[fib 5] --> F4[fib 4] & F3A[fib 3]
        F4 --> F3B[fib 3] & F2A[fib 2]
        F3A --> F2B[fib 2] & F1A[fib 1]
        F3B --> F2C[fib 2] & F1B[fib 1]
        note1[Same subproblems<br/>calculated repeatedly]
    end
    subgraph Memoised - Linear
        M5[fib 5] --> M4[fib 4] --> M3[fib 3] --> M2[fib 2] --> M1[fib 1]
        CACHE[(Memo cache<br/>results reused)]
        M2 & M3 & M4 --> CACHE
    end
style CACHE fill:#238636,color:#fff
style note1 fill:#f85149,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Naive recursion without memoisation for Fibonacci or similar — O(2ⁿ) instead of O(n).
• Allocating a full 2D DP table when only the previous row is needed — wastes O(n²) memory.
• Not identifying the recurrence relation before coding — DP without the relation is just guessing.
• Confusing DP with greedy algorithms — greedy makes locally optimal choices, DP explores all subproblems.

Code Examples

// Naive Fibonacci — O(2ⁿ) — recalculates same values exponentially:
function fib(int $n): int {
    if ($n <= 1) return $n;
    return fib($n - 1) + fib($n - 2); // fib(40) = ~1 billion calls
}

// Memoised — O(n) time, O(n) space:
function fib(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    return $memo[$n] ??= fib($n - 1, $memo) + fib($n - 2, $memo);
}

// Bottom-up tabulation — O(n) time, O(1) space:
function fibTab(int $n): int {
    [$a, $b] = [0, 1];
    for ($i = 2; $i <= $n; $i++) [$a, $b] = [$b, $a + $b];
    return $b;
}

References

• ↗ https://en.wikipedia.org/wiki/Dynamic_programming

Tags

Related Terms