Prestanite da učite DP formule napamet: Pravi način za učenje dinamičkog programiranja

Hajde da budemo brutalno iskreni. Dinamičko programiranje ima zastrašujuću reputaciju. Za mnoge programere, fraza “dinamičko programiranje” izaziva PTSP zurenja u praznu belu tablu tokom intervjua, dok intervjuer agresivno pročišćava grlo.

Mnogi misle da se DP svodi na zurenje u 2D Excel tabelu dok se matematička jednačina magično ne pojavi u viziji. Ili još gore, pokušavaju da formule nauče napamet!

Žao mi je što moram da vam saopštim loše vesti, ali to je najgori način za učenje!

Kako znam? Zato što su nas upravo tako učili na fakultetu, a ja sam urado loše ispit iz algoritama. Nedeljama sam pokušavao da zapamtim različite formule za tranziciju stanja, ubeđen da je moj mozak fundamentalno nekompatibilan sa računarstvom.

Dinamičko programiranje nije ništa više od pametne rekurzije. Bukvalno je samo začinjena rekurzija sa keširanjem. Ako možete da napišete rekurzivno brute force rešenje (a apsolutno možete), možete napisati i DP rešenje. To je mehanički prevod, korak po korak, a ne magični trik.

U ovom postu ćemo rešiti LeetCode 188: Best Time to Buy and Sell Stock IV. Nećemo početi crtanjem tabele. Počećemo sa jednostavnim stablom odlučivanja, naterati naš kod da shvati da ima amneziju i evoluirati naše rešenje u munjevito brzo, prostorno optimizovano remek-delo :D!

Postavka problema

Dat vam je niz celih brojeva prices gde je prices[i] cena akcije na i-ti dan, i ceo broj k.

Pronađite maksimalni profit koji možete ostvariti. Možete izvršiti najviše k transakcija. Napomena: Ne možete učestvovati u više transakcija istovremeno (tj. morate prodati akciju pre nego što je ponovo kupite).

Primer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

k = 2
prices = [3, 2, 6, 5, 0, 3]

Izlaz: 7
Objašnjenje: 
Kupite drugog dana (cena = 2) i prodajte trećeg dana (cena = 6)
profit = 6 - 2 = 4.
Zatim kupite petog dana (cena = 0) i prodajte šestog dana (cena = 3)
profit = 3 - 0 = 3.
Ukupan profit = 4 + 3 = 7.

Klasična Rekurzija (Brute Force)

Zaboravite na performanse na trenutak. Zamislite da ste putnik kroz vreme koji stoji na nultom danu. Koje izbore zapravo imate?

Poput Dr. Strejndža koji gleda u 14 miliona mogućih budućnosti, vaši izbori u potpunosti zavise od vašeg trenutnog stanja u vremenskoj liniji. Šta definiše vašu tačnu situaciju u bilo kom trenutku?

1. Trenutni dan (day): Koji je dan?
2. Preostalo transakcija (txLeft): Koliko puta još mogu da kupim?
3. Stanje držanja (holding): Da li trenutno posedujem akciju? (0 = Ne, 1 = Da).

Na osnovu ovog stanja, stablo odlučivanja je jednostavno:

• Ako nemamo akciju (Holding = 0):
  1. Preskoči: Ne radi ništa. Pređi na sledeći dan.
  2. Kupi: Potroši novac (-prices[day]), pređi na sledeći dan i zabeleži da sada držimo akciju. Ovo troši 1 token za transakciju.
• Ako imamo akciju (Holding = 1):
  1. Preskoči: Zadrži akciju i pređi na sledeći dan.
  2. Prodaj: Zaradi novac (+prices[day]), pređi na sledeći dan i zabeleži da više ne držimo akciju.

Pretvorimo ovu logiku u čistu, rekurzivnu C++ implementaciju.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // Počinjemo od nultog dana, sa k transakcija, ne držimo akciju
        return solve(0, k, 0, prices);
    }

private:
    int solve(int day, int txLeft, int holding, vector<int>& prices) {
        // Osnovni slučaj 1 - isteklo nam je vreme
        if (day == prices.size()) return 0;
        
        // Osnovni slučaj 2 - nemamo više tokena i ne držimo ništa za prodaju
        if (txLeft == 0 && holding == 0) return 0;

        // Izbor 1 - Ne radimo ništa danas. Samo putujemo kroz vreme do sutra
        int skip = solve(day + 1, txLeft, holding, prices);

        // Izbor 2 - Transakcija (Kupi ili Prodaj)
        int transact = 0;
        if (holding == 1) {
            // Imamo akciju! Prodajmo je da se obogatimo (+prices[day])
            transact = prices[day] + solve(day + 1, txLeft, 0, prices);
        }
        else {
            // Nemamo akciju. Kupimo jednu i gubimo novac danas (-prices[day])
            // Kupovina nas košta 1 token za transakciju
            transact = -prices[day] + solve(day + 1, txLeft - 1, 1, prices);
        }

        // Vraćamo vremensku liniju koja donosi najviše novca
        return max(skip, transact);
    }
};

Ovo rešenje je 100% logički ispravno. Takođe će 100% dovesti do greške Time Limit Exceeded.

Ima vremensku složenost od otprilike O(2^n). Za niz od 50 dana, ovo stablo će se razgranati u kvadrilione rekurzivnih poziva. Toplotna smrt univerzuma će nastupiti pre nego što se kod završi.

Memoizacija (Top-Down pristup)

Zašto je rekurzivno rešenje tako sporo? Zato što vaš kod ima ozbiljnu amneziju. Izračunava potpuno iste budućnosti iznova i iznova.

Zamislimo da stignete do 5. dana sa 1 preostalom transakcijom i posedujete akciju kroz dve potpuno različite vremenske linije:

1. Kupi 1. dana -> Prodaj 2. dana -> Kupi 5. dana.
2. Kupi 3. dana -> Prodaj 4. dana -> Kupi 5. dana.

Rekurzija ne zna da je već bila u ovom tačnom stanju. Ponovo izračunava celu budućnost od 5. dana do kraja niza, i to dva puta.

Da bismo ovo popravili, uvodimo koncept Keša (Memoizacija). Kada izračunamo odgovor za određeno stanje, zapišemo ga u našu beležnicu. Sledeći put kada dođemo u to isto stanje, samo pročitamo odgovor iz beležnice umesto da ga ponovo računamo.

Zlatno pravilo: Pamti budućnost, ignoriši prošlost

Ovo je deo koji zbunjuje skoro sve (uključujući i mene na fakultetu). Šta tačno čuvamo u ovoj beležnici?

Čuvamo budućnost, a ne prošlost.

Zamislite to kao da ste ubačeni u kazino u Las Vegasu. Funkcija solve(day, txLeft, holding) izračunava maksimalni profit koji možete ostvariti od danas do zatvaranja berze.

Berzu ne zanima kako ste stigli do 5. dana. Nije je briga da li ste zaradili bogatstvo 2. dana, ili izgubili životnu ušteđevinu 4. dana. Ako stojite 5. dana, sa jednim tokenom za transakciju, bez akcija, vaš budući potencijalni profit je potpuno isti bez obzira na prošlost.

Pošto prošlost nije bitna, možemo bezbedno keširati rezultat. Ako nas vremenska linija dovede do (dan 5, 1 token, 0 akcija), pogledamo u našu beležnicu: “Aha, ovo sam već izračunao. Iz ove tačne situacije, najviše novca koji mogu zaraditi do kraja igre je $10.” Bum. Pod-stablo je odsečeno.

Zašto 3D Keš?

Da bi naša beležnica radila, svako jedinstveno stanje treba svoj poseban slot za čuvanje odgovora.

Pogledajte potpis naše rekurzivne funkcije: solve(day, txLeft, holding). Niz prices se nikada ne menja, ali ostale tri promenljive da. Dakle, da bismo jedinstveno identifikovali našu tačnu situaciju, potreban nam je 3-dimenzionalni niz.

Zamislite to kao pronalaženje određenog sedišta u bioskopu:

1. Blok (day): Koji je dan? (Vrednosti od 0 do N)
2. Red (txLeft): Koliko tokena imamo? (Vrednosti od 0 do K)
3. Sedište (holding): Da li imamo akciju? (Vrednosti 0 ili 1)

Evo kako C++ kod izgleda kada mu damo memoriju:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    // Naša beležnica (3D keš)
    vector<vector<vector<int>>> memo;

public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        // [dani][transakcije][držanje]. Popunjavamo sa -1 (neizračunato)
        memo.assign(n, vector<vector<int>>(k + 1, vector<int>(2, -1)));
        
        return solve(0, k, 0, prices);
    }

    int solve(int day, int txLeft, int holding, vector<int>& prices) {
        if (day == prices.size() || (txLeft == 0 && holding == 0)) return 0;

        // Hej, da li smo već bili ovde? Proveri beležnicu!
        if (memo[day][txLeft][holding] != -1) {
            // Vrati keširani odgovor!
            return memo[day][txLeft][holding];
        }

        int skip = solve(day + 1, txLeft, holding, prices);

        int transact = 0;
        if (holding == 1) {
            transact = prices[day] + solve(day + 1, txLeft, 0, prices);
        }
        else {
            transact = -prices[day] + solve(day + 1, txLeft - 1, 1, prices);
        }

        // Pre vraćanja, zapiši odgovor u beležnicu za sledeći put
        return memo[day][txLeft][holding] = max(skip, transact);
    }
};

Složenost:

• Vreme: O(N * K). Svako stanje računamo tačno jednom!
• Prostor: O(N * K * 2) za 3D keš, plus memorija rekurzivnog steka.

Ovo će proći na LeetCode-u, ali možemo i bolje.

Tabelarni pristup (Bottom-Up pristup)

Rekurzija je super sve dok vam ulaz nije ogroman, stek poziva eksplodira i obori aplikaciju.

Tabelarni pristup (Tabulation) jednostavno znači popunjavanje te memo tabele pomoću for petlji umesto rekurzije.

U rekurziji smo počeli od 0. dana i gledali unapred. U tabelarnom pristupu, putujemo kroz vreme na kraj niza i radimo unazad do 0. dana.

Zašto unazad? Zato što da bismo znali najbolju odluku za 10. dan, moramo već znati optimalne budućnosti za 11. dan.

Prevedimo rekurzivnu logiku direktno u petlju:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    using table = vector<vector<vector<int>>>;
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // Kreiranje 3D DP tabele: dp[dan][transakcije][držanje]
        // Sve inicijalizujemo na 0 (automatski rešava osnovne slučajeve)
        table dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));

        // Petlja unazad od poslednjeg dana do nultog
        for (int day = n - 1; day >= 0; day--) {
            for (int txLeft = 1; txLeft <= k; txLeft++) {
                for (int holding = 0; holding <= 1; holding++) {
                    
                    // Izbor 1 - Preskoči (uzmi vrednost od sutra, isto stanje)
                    int skip = dp[day + 1][txLeft][holding];
                    
                    // Izbor 2 - Transakcija
                    int transact = 0;
                    if (holding == 1) {
                        // Prodaj
                        transact = prices[day] + dp[day + 1][txLeft][0];
                    }
                    else {
                        // Kupi
                        transact = -prices[day] + dp[day + 1][txLeft - 1][1];
                    }

                    // Sačuvaj najbolji izbor
                    dp[day][txLeft][holding] = max(skip, transact);
                }
            }
        }

        // Stanje sa kojim smo počeli: dan 0, k transakcija, držanje 0
        return dp[0][k][0]; 
    }
};

Optimizacija prostora

Pogledajte pažljivo petlju u tabelarnom kodu. Primetili ste nešto zanimljivo? Da bismo izračunali vrednosti za dan, gledamo samo vrednosti sa dan + 1. Ne zanimaju nas dan + 2, dan + 5 ili dan + 100.

Zašto držimo ceo 3D kalendar u memoriji kada nas zanimaju samo danas i sutra?

Možemo potpuno ukloniti dimenziju Dan iz našeg niza! Potrebna su nam samo 2D niza koji predstavljaju sledeciDan i trenutniDan. Dok se krećemo unazad kroz vreme, izračunavamo trenutniDan na osnovu sledecegDana, a zatim prepisujemo sledeciDan sa trenutnimDanom.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0 || k == 0) return 0;

        // Samo dva 2D niza: [držanje (0 ili 1)][transakcije (0 do K)]
        vector<vector<int>> nextDay(2, vector<int>(k + 1, 0));
        vector<vector<int>> currDay(2, vector<int>(k + 1, 0));

        for (int day = n - 1; day >= 0; day--) {
            for (int holding = 0; holding <= 1; holding++) {
                for (int txLeft = 1; txLeft <= k; txLeft++) {
                    
                    int skip = nextDay[holding][txLeft];
                    int transact = 0;

                    if (holding == 1) {
                        // Prodaj
                        transact = prices[day] + nextDay[0][txLeft];
                    }
                    else {
                        // Kupi
                        transact = -prices[day] + nextDay[1][txLeft - 1];
                    }

                    currDay[holding][txLeft] = max(skip, transact);
                }
            }
            // Krećemo se unazad kroz vreme za sledeću iteraciju petlje
            nextDay = currDay;
        }

        return currDay[0][k];
    }
};

Zaključak

Vidite kako smo potpuno izbegli zurenje u praznu belu tablu pokušavajući da izvlačimo matematičke formule iz vazduha?

Počeli smo sa osnovnom ljudskom logikom: Koji su moji izbori trenutno?

Napisali smo sporu rekurzivnu funkciju, dali joj beležnicu da pamti stvari (Memoizacija), pretvorili je u petlju (Tabelarni pristup) i odbacili delove beležnice koji nam više nisu bili potrebni (optimizacija prostora).

Tako se savladava dinamičko programiranje. Nije potrebna magija.