Dynamic Programming
debt(d7/e3/b3/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints list blackfire and xdebug as tools, but these only reveal exponential slowness at runtime under profiling — there is no static analysis that identifies overlapping subproblems. The automated flag is explicitly 'no', and the code pattern (recursive function with overlapping subproblems) requires a human reviewer to recognise the structural property. The problem is silent until scale reveals it.
Closest to 'simple parameterised fix' (e3). The quick_fix describes adding memoization (an array keyed by input) to an existing recursive function, or switching to tabulation. This is more than a one-line patch — it requires identifying the recurrence, adding a cache structure, and adjusting the recursive calls — but it is contained within a single function or component and does not require cross-cutting changes.
Closest to 'localised tax' (b3). DP applies to specific algorithmic functions (web/cli contexts) rather than being a system-wide architectural choice. Once a DP solution is correctly implemented, the rest of the codebase is unaffected; the burden is paying attention during the design of that one algorithm. The common mistake of allocating a full 2D table adds localised memory waste but does not propagate across the system.
Closest to 'notable trap' (t5). The misconception field states that developers commonly believe DP always requires a multidimensional array, when many problems only need O(n) or O(1) space. Additionally, common_mistakes highlight confusing DP with greedy algorithms and failing to identify the recurrence relation first. These are well-documented gotchas that most developers encounter, making this a notable but learnable trap rather than a catastrophic one.
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;
}