Programowanie dynamiczne – memoizacja, knapsack, LCS, dekorator memoize

Programowanie dynamiczne (DP) to technika rozwiązywania problemów przez rozbicie ich na podproblemy i zapamiętywanie wyników aby nie liczyć ich wielokrotnie. Brzmi abstrakcyjnie, ale w praktyce stosujesz DP kiedy piszesz cache dla kosztownej operacji albo szukasz optymalnego zestawu produktów do oferty. Pokazuję dwa klasyczne problemy z implementacją w PHP.

Memoizacja – DP od strony „top-down”

Klasyczny przykład: ciąg Fibonacciego. Wersja naiwna jest wykładnicza bo liczy te same wartości wielokrotnie:

<?php

// Naiwna rekurencja - O(2^n) - dramatycznie wolna
function fibNaive(int $n): int
{
    if ($n <= 1) {
        return $n;
    }

    // fib(40) to kilka miliardów wywołań!
    return fibNaive($n - 1) + fibNaive($n - 2);
}

// Memoizacja - zapamiętaj wyniki podproblemów - O(n)
function fibMemo(int $n, array &$memo = []): int
{
    if ($n <= 1) {
        return $n;
    }

    if (isset($memo[$n])) {
        return $memo[$n]; // wynik już obliczony - zwróć z cache
    }

    $memo[$n] = fibMemo($n - 1, $memo) + fibMemo($n - 2, $memo);
    return $memo[$n];
}

// Wersja iteracyjna "bottom-up" - O(n), O(1) pamięci
function fibIterative(int $n): int
{
    if ($n <= 1) {
        return $n;
    }

    $prev = 0;
    $curr = 1;

    for ($i = 2; $i <= $n; $i++) {
        [$prev, $curr] = [$curr, $prev + $curr];
    }

    return $curr;
}

echo fibMemo(50);      // 12586269025 - błyskawicznie
echo fibIterative(50); // 12586269025

Problem plecakowy – klasyczne DP

Problem plecakowy (knapsack): masz plecak o pojemności W i zestaw przedmiotów z wagami i wartościami. Wybierz przedmioty maksymalizujące wartość nie przekraczając pojemności.

Zastosowanie w e-commerce: dobieranie produktów do zestawu promocyjnego o ograniczonym budżecie, optymalizacja pakowania zamówień.

<?php

declare(strict_types=1);

function knapsack(array $items, int $capacity): array
{
    $n = count($items);

    // Tabela DP: dp[i][w] = max wartość używając pierwszych i przedmiotów z pojemnością w
    $dp = array_fill(0, $n + 1, array_fill(0, $capacity + 1, 0));

    for ($i = 1; $i <= $n; $i++) {
        $weight = $items[$i - 1]['weight'];
        $value  = $items[$i - 1]['value'];

        for ($w = 0; $w <= $capacity; $w++) {
            // Opcja 1: nie bierz przedmiotu i
            $dp[$i][$w] = $dp[$i - 1][$w];

            // Opcja 2: weź przedmiot i (jeśli się mieści)
            if ($weight <= $w) {
                $withItem   = $dp[$i - 1][$w - $weight] + $value;
                $dp[$i][$w] = max($dp[$i][$w], $withItem);
            }
        }
    }

    // Odtwórz które przedmioty zostały wybrane
    $selected = [];
    $w = $capacity;

    for ($i = $n; $i > 0; $i--) {
        if ($dp[$i][$w] !== $dp[$i - 1][$w]) {
            $selected[] = $items[$i - 1];
            $w -= $items[$i - 1]['weight'];
        }
    }

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

// Przykład: budżet marketingowy na zestaw produktów promocyjnych
// weight = cena zakupu (grosze), value = marża (grosze), capacity = budżet
$products = [
    ['name' => 'Kabel USB',     'weight' => 500,  'value' => 200],
    ['name' => 'Powerbank',     'weight' => 2000, 'value' => 900],
    ['name' => 'Słuchawki',     'weight' => 1500, 'value' => 700],
    ['name' => 'Etui na tel.',  'weight' => 800,  'value' => 350],
    ['name' => 'Ładowarka',     'weight' => 1200, 'value' => 500],
    ['name' => 'Uchwyt sam.',   'weight' => 900,  'value' => 400],
];

$budget = 3500; // 35 PLN w groszach

$result = knapsack($products, $budget);

echo "Maksymalna marża: " . ($result['max_value'] / 100) . " PLN\n";
echo "Wybrane produkty:\n";
foreach ($result['items'] as $item) {
    echo "  - " . $item['name'] . " (cena: " . ($item['weight'] / 100) . " PLN)\n";
}

Najdłuższy wspólny podciąg (LCS)

LCS to problem znajdowania najdłuższego ciągu elementów wspólnego dla dwóch sekwencji. Zastosowanie: diff między wersjami, wykrywanie podobieństwa tekstów, porównywanie list SKU:

<?php

declare(strict_types=1);

function longestCommonSubsequence(array $a, array $b): array
{
    $m  = count($a);
    $n  = count($b);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    // Wypełnij tabelę DP
    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]);
            }
        }
    }

    // Odtwórz LCS
    $lcs = [];
    $i   = $m;
    $j   = $n;

    while ($i > 0 && $j > 0) {
        if ($a[$i - 1] === $b[$j - 1]) {
            array_unshift($lcs, $a[$i - 1]);
            $i--;
            $j--;
        } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--;
        } else {
            $j--;
        }
    }

    return $lcs;
}

// Porównanie list produktów - które SKU są wspólne w zachowanej kolejności?
$oldCatalog = ['SKU-001', 'SKU-003', 'SKU-005', 'SKU-007', 'SKU-009'];
$newCatalog = ['SKU-001', 'SKU-002', 'SKU-005', 'SKU-006', 'SKU-007', 'SKU-010'];

$common = longestCommonSubsequence($oldCatalog, $newCatalog);
print_r($common);
// ['SKU-001', 'SKU-005', 'SKU-007'] - produkty zachowane w obu katalogach w tej samej kolejności

Memoizacja w PHP jako dekorator funkcji

<?php

// Generyczny dekorator memoizujący dla dowolnej funkcji
function memoize(callable $fn): callable
{
    $cache = [];

    return function() use ($fn, &$cache) {
        $args = func_get_args();
        $key  = serialize($args);

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

        return $cache[$key];
    };
}

// Kosztowne obliczenie - wywoła się tylko raz dla tych samych argumentów
$expensiveCalc = memoize(function(int $productId, string $currency): float {
    // Symulacja kosztownego przeliczenia kursu walut dla produktu
    sleep(0);
    return $productId * 1.23;
});

$price1 = $expensiveCalc(42, 'EUR'); // oblicza
$price2 = $expensiveCalc(42, 'EUR'); // z cache
$price3 = $expensiveCalc(43, 'EUR'); // oblicza (inny argument)

// Przydatne przy przetwarzaniu dużych zestawów danych
// gdzie ta sama wartość jest obliczana wielokrotnie

Kiedy stosować DP?

Programowanie dynamiczne ma sens gdy problem spełnia dwa warunki: optymalna podstruktura (optymalne rozwiązanie całości zawiera optymalne rozwiązania podproblemów) i pokrywające się podproblemy (te same podproblemy pojawiają się wielokrotnie). Jeśli rekurencja bez memoizacji jest wolna – to sygnał że DP może pomóc.

Podsumowanie

Programowanie dynamiczne to w praktyce połączenie rekurencji z inteligentnym cache. Memoizacja to najprostszy punkt wejścia - zapamiętaj wyniki kosztownych funkcji. Klasyczne problemy jak knapsack czy LCS pojawiają się w różnych przebraniach w prawdziwych projektach: optymalizacja zestawów produktów, porównywanie katalogów, obliczanie rabatów progowych. Znajomość techniki pozwala rozpoznać je i zastosować właściwe narzędzie.