Dynamic Programming w PHP – memoizacja i tabulacja w praktyce

Dynamic programming to technika rozwiązywania problemów przez rozbicie ich na mniejsze podproblemy i zapamiętanie wyników. W PHP stosuje się ją rzadziej niż w językach niskopoziomowych, ale pojawia się wszędzie tam gdzie naiwna rekursja jest za wolna. Pokazuję dwa podejścia: memoizację (top-down) i tabulację (bottom-up) na kilku konkretnych przykładach.

Problem z naiwną rekursją

Fibonacci to klasyczny przykład. Naiwna implementacja rekurencyjna ma złożoność O(2^n) – dla n=40 wykonuje ponad miliard wywołań:

<?php

// Naiwna rekursja - O(2^n), dla n=40 to 2^40 wywołań
function fibNaive(int $n): int
{
    if ($n <= 1) return $n;
    return fibNaive($n - 1) + fibNaive($n - 2);
}

// fibNaive(40) trwa kilka sekund
// fibNaive(50) - praktycznie nie do ukończenia w rozsądnym czasie

Memoizacja - top-down DP

Memoizacja polega na zapamiętaniu wyniku pierwszego wywołania i zwróceniu go przy kolejnych. Zmienia złożoność z O(2^n) na 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 - natychmiastowe

// Generyczna dekoracja memoizacją przez 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];
    };
}

// Problem: plecakowy (0/1 Knapsack) z memoizacją
// items: array of [weight, value], capacity: max weight
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

Tabulacja - bottom-up DP

Tabulacja buduje rozwiązanie od dołu, wypełniając tablicę wyników bez rekursji. Lepsza dla pamięci stosu przy dużych n:

<?php

declare(strict_types=1);

// Fibonacci - tabulacja
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];
}

// Optymalizacja pamięci - tylko dwie poprzednie wartości
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 (LCS) - tabulacja 2D
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 (BCBA lub BDAB)

// Coin change - minimalna liczba monet do wydania kwoty
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]; // grosze
echo coinChange($coins, 41); // 4 monet: 25 + 10 + 5 + 1

Kiedy stosować DP

DP jest właściwe gdy problem ma dwie cechy: optymalna podstruktura (optymalne rozwiązanie całości zależy od optymalnych rozwiązań podproblemów) i nakładające się podproblemy (te same podproblemy są rozwiązywane wielokrotnie). Typowe zastosowania w e-commerce i Magento: optymalizacja reguł cenowych (która kombinacja promocji daje najniższą cenę), łączenie produktów w bundle (plecakowy), Levenshtein dla wyszukiwania rozmytego.

<?php

// Praktyczny przykład: najlepsza kombinacja kuponów rabatowych
// Każdy kupon ma wartość i minimalną kwotę zamówienia
// Znajdź maksymalny łączny rabat możliwy do zastosowania

function maxDiscount(array $coupons, int $orderTotal): int
{
    // coupons: [['min_order' => 100, 'discount' => 15], ...]
    $n = count($coupons);
    // dp[i][total] = max rabat używając pierwszych i kuponów, wydając total
    // Uproszczony wariant: każdy kupon można użyć raz
    $dp = array_fill(0, $orderTotal + 1, 0);

    foreach ($coupons as $coupon) {
        // Iterujemy od góry żeby każdy kupon liczyć raz (0/1 knapsack)
        for ($t = $orderTotal; $t >= $coupon['min_order']; $t--) {
            $dp[$t] = max(
                $dp[$t],
                $dp[$t] + $coupon['discount'] // kupon nie zmienia kwoty zamówienia
            );
        }
    }

    return $dp[$orderTotal];
}

Wybór między memoizacją a tabulacją zależy od problemu. Memoizacja jest prostsza do napisania i liczy tylko potrzebne podproblemy (przydatne gdy nie wszystkie są wymagane). Tabulacja nie ma narzutu rekursji i łatwiej ją zoptymalizować pamięciowo przez rolling array.