Programowanie dynamiczne w C# — rekurencja i DP

Programowanie dynamiczne (DP) to technika rozwiązywania problemu przez rozbicie go na mniejsze podproblemy — ale to, co ją naprawdę definiuje, to zapamiętywanie wyniku każdego podproblemu, żeby nie liczyć go dwa razy. Zobaczmy to na konkretnym przykładzie, nie na metaforze.

Problem: minimalna liczba monet

Masz monety o nominałach 1, 5, 10, 25 groszy. Ile najmniej monet potrzebujesz, żeby wydać dokładnie 30 groszy?

Naiwna rekurencja — poprawna, ale wolna

static int NajmniejMonetNaiwnie(int[] nominaly, int kwota)
{
    if (kwota == 0) return 0;
    if (kwota < 0) return int.MaxValue - 1; // niemożliwe

    int min = int.MaxValue - 1;
    foreach (var nominal in nominaly)
    {
        int wynik = NajmniejMonetNaiwnie(nominaly, kwota - nominal);
        if (wynik + 1 < min) min = wynik + 1;
    }
    return min;
}

To rozwiązanie jest poprawne, ale dla kwota = 30 wywoła samo siebie dziesiątki tysięcy razy. Powód: żeby policzyć NajmniejMonetNaiwnie(20), funkcja wywołuje NajmniejMonetNaiwnie(19), NajmniejMonetNaiwnie(15), NajmniejMonetNaiwnie(10) — a każde z nich ponownie wywołuje np. NajmniejMonetNaiwnie(10) z zupełnie innej gałęzi rekurencji. Ten sam podproblem jest liczony od zera za każdym razem, gdy się pojawi — to jest dokładnie to, co nazywamy nakładającymi się podproblemami.

Memoizacja — zapamiętaj wynik, policz raz

static int NajmniejMonetMemo(int[] nominaly, int kwota, Dictionary<int, int> cache)
{
    if (kwota == 0) return 0;
    if (kwota < 0) return int.MaxValue - 1;
    if (cache.TryGetValue(kwota, out int zapamietany)) return zapamietany; // już liczone!

    int min = int.MaxValue - 1;
    foreach (var nominal in nominaly)
    {
        int wynik = NajmniejMonetMemo(nominaly, kwota - nominal, cache);
        if (wynik + 1 < min) min = wynik + 1;
    }

    cache[kwota] = min;
    return min;
}

Jedna dodana linijka logiki (cache.TryGetValue) zamienia algorytm z wykładniczego na liniowy względem kwota. Każdy podproblem (kwota = 0, 1, 2, ..., 30) zostaje policzony dokładnie raz — kolejne wywołania z tą samą wartością kwota odczytują gotowy wynik z cache zamiast liczyć go od nowa.

Tabulacja — to samo, ale od dołu do góry

static int NajmniejMonetTabulacja(int[] nominaly, int kwota)
{
    var dp = new int[kwota + 1];
    Array.Fill(dp, int.MaxValue - 1);
    dp[0] = 0; // 0 monet, żeby wydać 0

    for (int i = 1; i <= kwota; i++)
    {
        foreach (var nominal in nominaly)
        {
            if (nominal <= i && dp[i - nominal] + 1 < dp[i])
                dp[i] = dp[i - nominal] + 1;
        }
    }

    return dp[kwota];
}

Zamiast rekurencji “od góry” (od kwota w dół do 0), tabulacja liczy “od dołu” — najpierw dp[0], potem dp[1], aż do dp[kwota]. Wynik identyczny jak w memoizacji, ale bez ryzyka przepełnienia stosu wywołań dla dużych kwot i bez narzutu na wywołania rekurencyjne — w praktyce to najczęściej wybierana forma DP w kodzie produkcyjnym.

Dwie właściwości DP — na tym samym przykładzie

Nakładające się podproblemy: dp[15] jest potrzebny do policzenia zarówno dp[20] (przez monetę 5), jak i dp[16] (przez monetę 1) — ten sam podproblem pojawia się w wielu miejscach większego problemu.

Optymalna podstruktura: najlepsze rozwiązanie dla kwota = 30 da się zbudować z najlepszych rozwiązań dla mniejszych kwot (dp[29], dp[25], dp[20] — zależnie od monety). Gdyby optymalne rozwiązanie dla 30 wymagało nieoptymalnego rozwiązania dla 25, DP by nie zadziałało — cały algorytm opiera się na tym, że optymalne rozwiązania mniejszych podproblemów składają się na optymalne rozwiązanie całości.

Kiedy sięgnąć po DP

Rozpoznaj problem po charakterystycznych pytaniach: “ile sposobów da się to zrobić?”, “jaka jest minimalna/maksymalna wartość?”, “czy da się to osiągnąć w ogóle?” — połączone z tym, że rozwiązanie większego problemu naturalnie rozkłada się na te same, mniejsze decyzje (jak w monetach: “którą monetę wziąć teraz?”). Najprostszy klasyczny przykład tego wzorca zobaczysz w Ciągu Fibonacciego, gdzie ten sam mechanizm memoizacji przyspiesza liczenie n-tego wyrazu z czasu wykładniczego do liniowego.

Podsumowanie

Programowanie dynamiczne to nie osobna, mistyczna technika — to naiwna rekurencja plus jedna zmiana: zapamiętywanie wyników podproblemów, żeby nigdy nie liczyć tego samego dwa razy. Memoizacja robi to “od góry” (dodając cache do rekurencji), tabulacja robi to “od dołu” (wypełniając tablicę w pętli) — obie dają ten sam wynik, tabulacja jest zwykle szybsza i bezpieczniejsza w produkcji. Rozpoznajesz kandydata na DP, gdy problem pyta o optimum/liczbę sposobów i naturalnie rozkłada się na powtarzające się mniejsze decyzje.

Powiązane: memoizacja z DP przydaje się w zadaniu rekrutacyjnym Ciąg Fibonacciego. Zobacz też klasyfikację algorytmów.