Dynamic programming is a technique for solving problems by breaking them into smaller subproblems and caching the results. It’s used less frequently in PHP than in lower-level languages, but shows up wherever naive recursion is too slow. I cover two approaches: memoization (top-down) and tabulation (bottom-up) through concrete examples.
The problem with naive recursion
Fibonacci is the classic example. Naive recursive implementation runs in O(2^n) – for n=40 it makes over a billion calls:
<?php
// Naive recursion - O(2^n), for n=40 that's 2^40 calls
function fibNaive(int $n): int
{
if ($n <= 1) return $n;
return fibNaive($n - 1) + fibNaive($n - 2);
}
// fibNaive(40) takes several seconds
// fibNaive(50) - practically impossible to finish in reasonable time
Memoization - top-down DP
Memoization caches the result of the first call and returns it on subsequent calls. Reduces complexity from O(2^n) to O(n):
<?php
declare(strict_types=1);
class Memoizer
{
private array $cache = [];
public function fib(int $n): int
{
if ($n <= 1) return $n;
if (isset($this->cache[$n])) {
return $this->cache[$n];
}
$this->cache[$n] = $this->fib($n - 1) + $this->fib($n - 2);
return $this->cache[$n];
}
}
$m = new Memoizer();
echo $m->fib(50); // 12586269025 - instant
// Generic memoization via closure
function memoize(callable $fn): callable
{
$cache = [];
return function () use ($fn, &$cache) {
$key = serialize(func_get_args());
if (!array_key_exists($key, $cache)) {
$cache[$key] = $fn(...func_get_args());
}
return $cache[$key];
};
}
// 0/1 Knapsack with memoization
function knapsack(array $items, int $capacity, int $idx, array &$memo): int
{
if ($idx < 0 || $capacity === 0) return 0;
$key = "{$idx},{$capacity}";
if (isset($memo[$key])) return $memo[$key];
$withoutItem = knapsack($items, $capacity, $idx - 1, $memo);
$withItem = 0;
if ($items[$idx]['weight'] <= $capacity) {
$withItem = $items[$idx]['value'] + knapsack(
$items,
$capacity - $items[$idx]['weight'],
$idx - 1,
$memo
);
}
$memo[$key] = max($withoutItem, $withItem);
return $memo[$key];
}
$items = [
['weight' => 2, 'value' => 6],
['weight' => 2, 'value' => 10],
['weight' => 3, 'value' => 12],
['weight' => 5, 'value' => 15],
];
$memo = [];
echo knapsack($items, 5, count($items) - 1, $memo); // 22
Tabulation - bottom-up DP
Tabulation builds the solution from the bottom up, filling a results table without recursion. Better for call stack at large n:
<?php
declare(strict_types=1);
// Fibonacci - tabulation
function fibTabulation(int $n): int
{
if ($n <= 1) return $n;
$dp = array_fill(0, $n + 1, 0);
$dp[1] = 1;
for ($i = 2; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] + $dp[$i - 2];
}
return $dp[$n];
}
// Memory optimisation - only two previous values
function fibOptimal(int $n): int
{
if ($n <= 1) return $n;
$prev2 = 0;
$prev1 = 1;
for ($i = 2; $i <= $n; $i++) {
$curr = $prev1 + $prev2;
$prev2 = $prev1;
$prev1 = $curr;
}
return $prev1;
}
// Longest Common Subsequence - 2D tabulation
function lcs(string $a, string $b): int
{
$m = strlen($a);
$n = strlen($b);
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($a[$i - 1] === $b[$j - 1]) {
$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
} else {
$dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
}
}
}
return $dp[$m][$n];
}
echo lcs('ABCBDAB', 'BDCABA'); // 4
// Coin change - minimum coins to make amount
function coinChange(array $coins, int $amount): int
{
$dp = array_fill(0, $amount + 1, PHP_INT_MAX);
$dp[0] = 0;
for ($i = 1; $i <= $amount; $i++) {
foreach ($coins as $coin) {
if ($coin <= $i && $dp[$i - $coin] !== PHP_INT_MAX) {
$dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
}
}
}
return $dp[$amount] === PHP_INT_MAX ? -1 : $dp[$amount];
}
$coins = [1, 5, 10, 25];
echo coinChange($coins, 41); // 4 coins: 25 + 10 + 5 + 1
When to use DP
DP applies when a problem has two properties: optimal substructure (optimal solution of the whole depends on optimal solutions of subproblems) and overlapping subproblems (same subproblems solved repeatedly). Typical uses in e-commerce and Magento: pricing rule optimisation (which promotion combination gives the lowest price), bundle product selection (knapsack), Levenshtein distance for fuzzy search.
Choice between memoization and tabulation depends on the problem. Memoization is simpler to write and only computes needed subproblems. Tabulation has no recursion overhead and is easier to memory-optimise via rolling arrays.
