Dynamic programming – memoization, knapsack, LCS, memoize decorator

Dynamic programming is one of those techniques that sounds intimidating but is built on one simple idea: remember results you have already computed so you do not compute them again. Memoization, the knapsack problem, Longest Common Subsequence – I implement them all in PHP and show a reusable memoize decorator that works with any callable.

The core idea – overlapping subproblems

<?php

// Classic example: Fibonacci without memoization
// fib(5) computes fib(3) twice, fib(2) three times, etc.
// Complexity: O(2^n) - exponential
function fib(int $n): int
{
    if ($n <= 1) return $n;
    return fib($n - 1) + fib($n - 2);
}

// With memoization - store computed results
// Complexity: O(n) - each value computed exactly once
function fibMemo(int $n, array &$memo = []): int
{
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fibMemo($n - 1, $memo) + fibMemo($n - 2, $memo);
}

echo fib(10);      // 55 - slow for large n
echo fibMemo(40);  // 102334155 - instant
echo fibMemo(100); // 354224848179261915075 - no problem

Memoize decorator - reusable for any callable

<?php

declare(strict_types=1);

class Memoize
{
    private array $cache = [];

    public function __construct(private callable $fn) {}

    public function __invoke(mixed ...$args): mixed
    {
        $key = serialize($args);

        if (!array_key_exists($key, $this->cache)) {
            $this->cache[$key] = ($this->fn)(...$args);
        }

        return $this->cache[$key];
    }

    // Factory method
    public static function wrap(callable $fn): static
    {
        return new static($fn);
    }
}

// Wrap any expensive function
$expensiveQuery = Memoize::wrap(function(int $productId): array {
    // Imagine this hits the database
    return ['id' => $productId, 'name' => "Product {$productId}", 'price' => 99.99];
});

$product = $expensiveQuery(42); // DB query
$product = $expensiveQuery(42); // returns cached result - no DB query
$product = $expensiveQuery(99); // different args - DB query

// Memoize with time-to-live
class TtlMemoize extends Memoize
{
    private array $timestamps = [];

    public function __construct(callable $fn, private int $ttlSeconds = 300) {
        parent::__construct($fn);
    }

    public function __invoke(mixed ...$args): mixed
    {
        $key = serialize($args);
        $now = time();

        if (isset($this->timestamps[$key]) && ($now - $this->timestamps[$key]) < $this->ttlSeconds) {
            return $this->cache[$key];
        }

        $this->cache[$key]      = ($this->fn)(...$args);
        $this->timestamps[$key] = $now;
        return $this->cache[$key];
    }
}

Knapsack problem - 0/1 variant

<?php

// Items with weight and value, limited capacity
// Which items to take to maximise value?
// Practical use: order fulfilment with weight limit, resource allocation

function knapsack(array $items, int $capacity): array
{
    $n  = count($items);
    $dp = array_fill(0, $n + 1, array_fill(0, $capacity + 1, 0));

    // Build the DP table
    for ($i = 1; $i <= $n; $i++) {
        ['weight' => $w, 'value' => $v] = $items[$i - 1];
        for ($c = 0; $c <= $capacity; $c++) {
            if ($w > $c) {
                $dp[$i][$c] = $dp[$i - 1][$c]; // cannot take this item
            } else {
                $dp[$i][$c] = max(
                    $dp[$i - 1][$c],           // skip item
                    $dp[$i - 1][$c - $w] + $v  // take item
                );
            }
        }
    }

    // Backtrack to find which items were taken
    $taken = [];
    $c     = $capacity;
    for ($i = $n; $i > 0; $i--) {
        if ($dp[$i][$c] !== $dp[$i - 1][$c]) {
            $taken[] = $items[$i - 1]['name'];
            $c      -= $items[$i - 1]['weight'];
        }
    }

    return ['max_value' => $dp[$n][$capacity], 'items' => array_reverse($taken)];
}

$items = [
    ['name' => 'Laptop',    'weight' => 3,  'value' => 4000],
    ['name' => 'Phone',     'weight' => 1,  'value' => 1500],
    ['name' => 'Tablet',    'weight' => 2,  'value' => 2000],
    ['name' => 'Headphones','weight' => 1,  'value' => 500],
    ['name' => 'Camera',    'weight' => 2,  'value' => 1800],
];

$result = knapsack($items, 5); // max weight 5kg
echo "Max value: " . $result['max_value'] . " PLN\n"; // 5800
echo "Items: " . implode(', ', $result['items']) . "\n"; // Phone, Tablet, Camera

Longest Common Subsequence (LCS)

<?php

// LCS - longest sequence present in both strings in the same order
// Practical use: diff algorithms, plagiarism detection, DNA comparison
function lcs(string $a, string $b): string
{
    $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]);
            }
        }
    }

    // Reconstruct the sequence
    $result = '';
    $i = $m; $j = $n;
    while ($i > 0 && $j > 0) {
        if ($a[$i - 1] === $b[$j - 1]) {
            $result = $a[$i - 1] . $result;
            $i--; $j--;
        } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--;
        } else {
            $j--;
        }
    }

    return $result;
}

echo lcs('ABCBDAB', 'BDCAB'); // 'BCAB' - length 4
echo lcs('magento2', 'magent'); // 'magent' - length 6

When to apply dynamic programming

• Optimal substructure: the optimal solution to the whole problem contains optimal solutions to its sub-problems
• Overlapping subproblems: the same sub-problems are solved multiple times without memoization
• If only one of these holds, greedy algorithms or divide-and-conquer may be better

Summary

Dynamic programming reduces exponential algorithms to polynomial time by trading memory for speed. The memoize decorator makes it easy to apply to any existing function. Knapsack and LCS are the canonical examples, but the pattern appears wherever you can identify overlapping subproblems - pricing engine with tiered rules, edit distance for fuzzy search, shortest path with constraints.