Uvod u dinamičko programiranje (DP)

Dinamičko programiranje (DP) je tehnika optimizacije problema koji se mogu podeliti na manje, preklapajuće podprobleme sa optimalnom podstrukturom. Ova lekcija kombinuje teoriju, vizualizaciju stanja DP i interaktivne primere kako bi učenici lakše razumeli koncept.

1. Preklapanje podproblema i optimalna podstruktura

Svaki problem koji rešavamo DP-om zadovoljava dve ključne osobine:

Optimalna podstruktura: optimalno rešenje celog problema se može dobiti iz optimalnih rešenja njegovih podproblema.
Preklapanje podproblema: isti podproblem se pojavljuje više puta; čuvanjem rezultata izbegavamo ponovljene izračune.

Vizualni primer: Fibonacci niz


// Fib(5) rekuzivno:
// fib(5)
// ├─ fib(4)
// │  ├─ fib(3)
// │  │  ├─ fib(2)
// │  │  └─ fib(1)
// │  └─ fib(2) <- ovo se ponavlja
// └─ fib(3) <- ovo se ponavlja

Napomena: memoizacija sprečava višestruko računanje istih čvorova u stablu rekurzije.

2. Top-down (memoizacija) vs Bottom-up (tabulacija)

Top-down: rekurzija + čuvanje rezultata podproblema u nizu ili mapi.


int fib(int n, vector& memo) {
    if(n <= 1) return n;
    if(memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

Bottom-up: iterativno gradimo rešenja od najmanjih podproblema prema većim, bez rekurzije.


int fibTab(int n) {
    vector dp(n+1);
    dp[0] = 0; dp[1] = 1;
    for(int i=2; i<=n; ++i)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

Vizualizacija tabulacije: dp niz = [0, 1, 1, 2, 3, 5]

3. Jednostavni primeri za vežbu

3.1 Broj načina da se popne stepenik


// DP niz dp[i] = broj načina da se popne i-ti stepenik
dp[0] = 1;
dp[1] = 1;
for i = 2 do N:
    dp[i] = dp[i-1] + dp[i-2];

Vizualizacija za N = 5: dp = [1, 1, 2, 3, 5, 8]

3.2 Maksimalna suma podniza


// dp[i] = maksimalna suma podniza koja se završava u i-tom elementu
dp[0] = nums[0];
for i = 1 to n-1:
    dp[i] = max(nums[i], dp[i-1] + nums[i]);
maks = max(dp[0..n-1]);

Vizualizacija: nums = [3, -1, 4, -2, 5] → dp = [3, 2, 6, 4, 9]

4. Predlozi za vežbu (interaktivni)

Izračunaj broj načina da se popne stepenik sa 10 stepenika koristeći memoizaciju i tabulaciju.
Pronađi maksimalnu sumu podniza niza {3, -1, 4, -2, 5}.
Napiši DP funkciju za minimum broja novčića potrebnog da se dobije određeni iznos (Coin Change problem).
Prikaži vizualno dp niz za svaki korak algoritma (može koristiti print ili konzolu).

5. Dodatni resursi

Stranica za ovu lekciju: /uvod_u_dp.html

Primeri dinamičkog programiranja — nivo državnog takmičenja

U ovom odeljku prikazaćemo dva tipična problema za učenike 8. razreda ili 1. razreda srednje škole, rešena dinamičkim programiranjem (DP) u C++. Svaki primer sadrži objašnjenje korak po korak, DP niz i implementaciju.

Primer 1 — Broj načina da se popne stepenik (Staircase problem)

Zadatak: Imaš N stepenika. Možeš da se popneš po 1 ili 2 stepenika u jednom potezu. Izračunaj broj različitih načina da se popneš do vrha.

Analiza problema:

Da bi došao do i-tog stepenika, možeš doći sa (i-1)-tog stepenika ili (i-2)-tog stepenika.
Preklapanje podproblema: broj načina za (i-1) i (i-2) se ponovo koristi za veći i.
Optimalna podstruktura: broj načina za i zavisi samo od prethodna dva rešenja.


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cout << "Unesi broj stepenika: ";
    cin >> N;

    if(N == 0) { cout << 0; return 0; }

    vector<int> dp(N+1);
    dp[0] = 1;  // 1 način da se ostane na tlu
    dp[1] = 1;  // 1 način da se popne prvi stepenik

    for(int i = 2; i <= N; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << "Broj načina: " << dp[N] << endl;
    return 0;
}

Objašnjenje: - dp[i] čuva broj načina da se dođe do i-tog stepenika. - Početni uslovi dp[0] = 1, dp[1] = 1. - Iterativno računamo dp[i] = dp[i-1] + dp[i-2]. - Na kraju dp[N] sadrži konačan broj načina.

Primer 2 — Maksimalna suma podniza (Maximum Subarray Sum)

Zadatak: Dat je niz celih brojeva. Pronađi sumu najvećeg kontinualnog podniza.

Analiza problema:

dp[i] = maksimalna suma podniza koji se završava na i-tom elementu.
Optimalna podstruktura: dp[i] zavisi samo od dp[i-1] i trenutnog elementa.
Preklapanje podproblema: svaka suma koristi prethodno rešenje dp[i-1].


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {3, -1, 4, -2, 5};
    int n = nums.size();

    vector<int> dp(n);
    dp[0] = nums[0];
    int maks = dp[0];

    for(int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        maks = max(maks, dp[i]);
    }

    cout << "Maksimalna suma podniza: " << maks << endl;
    return 0;
}

Objašnjenje: - Za prvi element dp[0] = nums[0]. - Za svaki sledeći element dp[i] = max(nums[i], dp[i-1] + nums[i]) — biramo da li da počnemo novi podniz ili nastavimo prethodni. - Maksimalna vrednost u dp nizu je tražena suma.

Ovi primeri pokrivaju osnovne tehnike DP: broj načina (preklapanje i optimalna podstruktura) i maksimalnu sumu podniza (iterativna tabulacija). Takvi problemi se često javljaju na državnim takmičenjima i pripremaju učenike za složenije DP zadatke.

Primer 3 — Broj načina da se dobije suma (Coin Change)

Zadatak: Dat je niz kovanica različitih vrednosti i ukupna suma S. Nađi na koliko različitih načina se može složiti suma S koristeći kovanice. Svaka kovanica može biti korišćena više puta.

Analiza problema:

Preklapanje podproblema: broj načina da se dobije suma S zavisi od broja načina za manje sume.
Optimalna podstruktura: za svaku sumu možemo dodati kovanicu i kombinovati prethodna rešenja.
DP niz dp[i] čuva broj načina da se dobije suma i.


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, S;
    cout << "Unesi broj vrsta kovanica: ";
    cin >> n;
    vector<int> coins(n);
    cout << "Unesi vrednosti kovanica: ";
    for(int i = 0; i < n; i++) cin >> coins[i];

    cout << "Unesi sumu: ";
    cin >> S;

    vector<int> dp(S+1, 0);
    dp[0] = 1;  // postoji 1 način da se dobije suma 0

    for(int i = 0; i < n; i++) {
        for(int s = coins[i]; s <= S; s++) {
            dp[s] += dp[s - coins[i]];
        }
    }

    cout << "Broj načina da se dobije suma " << S << ": " << dp[S] << endl;
    return 0;
}

Objašnjenje:

dp[0] = 1 jer postoji samo jedan način da se ne uzme nijedna kovanica.
Za svaku kovanicu coins[i] prolazimo kroz sve sume od coins[i] do S.
Za sumu s, dodajemo broj načina dp[s - coins[i]] jer ako složimo tu sumu sa ovom kovanicom, dobijamo novu kombinaciju.
Na kraju, dp[S] sadrži ukupan broj različitih kombinacija koje daju sumu S.

Ovaj zadatak uvodi učenike u **DP sa više poteza** i **kombinatoriku kombinacija**, što je čest tip problema na državnim takmičenjima.

Ograničenja dinamičkog programiranja (DP)

Dinamičko programiranje je moćna tehnika za rešavanje optimizacionih i kombinatornih problema, ali nije univerzalno rešenje. Postoje situacije u kojima DP nije primenljiv ili može biti neefikasan. U nastavku su najvažnija ograničenja DP-a koja učenici treba da razumeju.

Nema preklapanja podproblema – Ako se podproblemi ne ponavljaju (kao kod „divide and conquer“ pristupa), tada DP ne donosi nikakvu uštedu; često je klasična rekurzija ili drugi algoritam brži.
Nema optimalne podstrukture – DP se oslanja na to da se optimalno rešenje može dobiti kombinovanjem optimalnih rešenja podproblema. Ako to ne važi (npr. problemi gde lokalno optimalno vodi u globalno loše rešenje), DP neće raditi.
Potrošnja memorije može biti velika – DP tabele mogu imati hiljade ili milione stanja. Kod problema sa dva ili više dimenzija, memorija eksponencijalno raste (npr. DP[n][sum]).
Prevelik broj stanja – Ako je broj stanja ogroman (npr. stotine hiljada ili više), vreme izvršavanja postaje neupotrebljivo, čak i ako je svaki korak O(1).
Teško definisanje stanja – Kod nekih problema teško je definisati jasna DP stanja ili prelaze između njih. Često sam pokušaj pravljenja DP formulacije može biti složeniji od samog problema.
Neefikasan kod problema sa kontinuiranim vrednostima – DP obično radi nad diskretnim stanjima. Ako problem uključuje realne brojeve, opseg može biti beskonačan i DP postaje nepraktičan.
Složeni prelazi – Ako su prelazi između stanja preskupi (npr. svako stanje zahteva iteraciju kroz 1000 drugih), DP formula postaje spora i nije izvodljiva.

Razumevanje ovih ograničenja pomaže učenicima da prepoznaju kada je DP pravo rešenje, a kada treba koristiti druge tehnike poput heuristika, greedy pristupa, graf algoritama ili rekurzivnog „divide and conquer“.

DP vs. Greedy vs. Divide & Conquer

Kratak pregled najvažnijih razlika između ove tri ključne tehnike rešavanja algoritamskih problema. Tabela pomaže učenicima da pravilno izaberu odgovarajući pristup u zavisnosti od strukture problema.

Tehnika	Kada se koristi	Prednosti	Nedostaci	Primeri problema
Dinamičko programiranje (DP)	Problemi sa preklapanjem podproblema i optimalnom podstrukturom.	– optimalna rešenja – dobro za kombinatorne probleme – rešava kompleksne zadatke kao što su rasporedi i putanje	– ponekad velika memorija – teško definisanje stanja – sporije od greedy metoda	Fibonacci, Knapsack, LCS, najkraće putanje (DAG)
Greedy algoritmi	Problemi gde lokalni optimum vodi ka globalno optimalnom rešenju.	– veoma brzi (često O(n log n) ili bolje) – jednostavni za implementaciju – dobra aproksimacija kad optimalno nije moguće	– ne garantuju optimalnost uvek – zahtevaju posebnu strukturu problema	Kruskall, Prim, Huffman, aktivnosti (Activity Selection)
Divide & Conquer	Problemi koji se mogu podeliti na međusobno nezavisne podprobleme.	– efikasno rešavanje velikih problema – koristi paralelizam – često veoma elegantna rešenja	– ne pomaže ako se podproblemi preklapaju (tada DP pobedjuje) – ponekad komplikovana rekurzija	MergeSort, QuickSort, binarna pretraga, FFT

Vremenska i prostorna složenost u dinamičkom programiranju

Dinamičko programiranje omogućava značajno ubrzanje algoritama, ali često dolazi uz povećanu potrošnju memorije. Razumevanje složenosti i načina optimizacije je ključno za primenu DP-a na realnim problemima.

Vremenska složenost

Vremenska složenost DP algoritama obično je proporcionalna broju stanja i broju tranzicija između njih. Kod najčešćih primena, složenost je:

O(n) — najjednostavniji linearni DP (npr. fibonaci u iterativnoj verziji)
O(n · k) — problemi gde svako stanje ima ograničen broj prelaza
O(n²) ili više — tipično kod problema sa segmentima, intervalima, matrice

Prostorna složenost

Prostorna složenost DP-a zavisi od veličine DP tabele. Često:

O(n) — kod optimizovanih linearnih DP modela
O(n · k) — kod kombinatornih i knapsack varijanti
O(n²) — kod DP-a nad intervalima ili 2D podproblemima

Saveti za optimizaciju DP algoritama

1. Iterativna tabulacija umesto rekuzije sa memoizacijom

Kada je moguće, koristi iterativnu bottom-up implementaciju. Ona je brža, efikasnija i izbegava probleme poput prevelike dubine steka.

2. Smanjenje memorije (space optimization)

U mnogim DP modelima nije potrebna cela tabela — već samo poslednji ili poslednja dva reda. Tipični primeri:

Fibonaci — sa O(n) na O(1)
Knapsack — 2D tabelu svesti na 1D niz
LCS/LIS — delimično smanjenje memorije

3. Testiranje za velike ulaze

Pre primene DP rešenja na takmičarskim ili realnim podacima, proveriti:

da li DP tabela može stati u memoriju (posebno za 2D matrice)
koliko prelaza po stanju postoji
da li je potrebno koristiti modularnu aritmetiku kod velikih brojeva

4. Prepoznavanje nepotrebnih stanja

Često DP tabela sadrži više stanja nego što je stvarno potrebno. Pre uklanjanja memorije, identifikovati koja stanja su zaista dostižna ili korisna.

5. Kompresija stanja i optimizacija prelaza

Kod složenijih problema (npr. DP nad bitmaskama), moguće je smanjiti memoriju tako što se stanja kodiraju manjim brojem bitova ili koriste efikasnije strukture.

Razumevanje ovih principa omogućava primenu dinamičkog programiranja i na vrlo velike probleme, bez usporavanja programa ili prevelike potrošnje memorije.

Preporučeni izvori za učenje dinamičkog programiranja

Za dublje razumevanje DP tehnika, korisno je učiti iz različitih formata: tekstualnih tutorijala, video lekcija i interaktivnih platformi. Slede pažljivo odabrani kvalitetni izvori koji pokrivaju i osnovne i napredne teme.

Tekstualni tutorijali i članci

CP-Algorithms — Dynamic Programming — jedno od najjasnijih i najpopularnijih objašnjenja DP tehnika.
GeeksForGeeks — Dinamičko programiranje — veliki broj praktičnih primera i rešenih zadataka.
LeetCode Learn — DP kartica — vodič kroz osnovne i srednje složene DP probleme.

Video predavanja

WilliamFiset — Dynamic Programming playlist — jasna objašnjenja sa vizualizacijama.
MIT OpenCourseWare — DP intro — univerzitetsko predavanje sa primerima.
Errichto — DP for Competitive Programming — fokus na takmičarskom programiranju.

Interaktivne platforme

USACO Guide — Interactive DP lessons — interaktivni zadaci sa objašnjenjima.
HackerRank DP Challenges — postepeno ređani zadaci za vežbu.
Codeforces — DP Problems — veliki izbor zadataka različitog nivoa.

Preporučene knjige

Introduction to Algorithms (CLRS) — najpoznatiji univerzitetski udžbenik, detaljno pokriva DP.
The Algorithm Design Manual — Skiena — praktičan pristup rešavanju problema, uključuje i DP metode.
Algorithm Design — Kleinberg & Tardos — odlična knjiga za intuitivno razumevanje tehnika, uključujući DP.

Istraživanje ovih izvora pomoći će učenicima da prošire znanje o dinamičkom programiranju i steknu sigurnost u rešavanju različitih problema.

Prethodno
|< Rekurzivni algoritmi

Sledeće
DP: Fibonacci sa memoizacijom >|

Uvod u dinamičko programiranje (DP)

1. Preklapanje podproblema i optimalna podstruktura

2. Top-down (memoizacija) vs Bottom-up (tabulacija)

3. Jednostavni primeri za vežbu

3.1 Broj načina da se popne stepenik

3.2 Maksimalna suma podniza

4. Predlozi za vežbu (interaktivni)

5. Dodatni resursi

Primeri dinamičkog programiranja — nivo državnog takmičenja

Primer 1 — Broj načina da se popne stepenik (Staircase problem)

Primer 2 — Maksimalna suma podniza (Maximum Subarray Sum)

Primer 3 — Broj načina da se dobije suma (Coin Change)

Ograničenja dinamičkog programiranja (DP)

DP vs. Greedy vs. Divide & Conquer

Vremenska i prostorna složenost u dinamičkom programiranju

Vremenska složenost

Prostorna složenost

Saveti za optimizaciju DP algoritama

1. Iterativna tabulacija umesto rekuzije sa memoizacijom

2. Smanjenje memorije (space optimization)

3. Testiranje za velike ulaze

4. Prepoznavanje nepotrebnih stanja

5. Kompresija stanja i optimizacija prelaza

Skriveni mini kviz — Dinamičko programiranje (DP)

Mini kviz: Da li razumeš osnove DP?

Mini zadaci za samostalan rad

Preporučeni izvori za učenje dinamičkog programiranja

Tekstualni tutorijali i članci

Video predavanja

Interaktivne platforme

Preporučene knjige

Uvod u dinamičko programiranje (DP)

1. Preklapanje podproblema i optimalna podstruktura

2. Top-down (memoizacija) vs Bottom-up (tabulacija)

3. Jednostavni primeri za vežbu

3.1 Broj načina da se popne stepenik

3.2 Maksimalna suma podniza

4. Predlozi za vežbu (interaktivni)

5. Dodatni resursi

Primeri dinamičkog programiranja — nivo državnog takmičenja

Primer 1 — Broj načina da se popne stepenik (Staircase problem)

Primer 2 — Maksimalna suma podniza (Maximum Subarray Sum)

Primer 3 — Broj načina da se dobije suma (Coin Change)

Ograničenja dinamičkog programiranja (DP)

DP vs. Greedy vs. Divide & Conquer

Vremenska i prostorna složenost u dinamičkom programiranju

Vremenska složenost

Prostorna složenost

Saveti za optimizaciju DP algoritama

1. Iterativna tabulacija umesto rekuzije sa memoizacijom

2. Smanjenje memorije (space optimization)

3. Testiranje za velike ulaze

4. Prepoznavanje nepotrebnih stanja

5. Kompresija stanja i optimizacija prelaza

Skriveni mini kviz — Dinamičko programiranje (DP)

Mini kviz: Da li razumeš osnove DP?

Mini zadaci za samostalan rad

Preporučeni izvori za učenje dinamičkog programiranja

Tekstualni tutorijali i članci

Video predavanja

Interaktivne platforme

Preporučene knjige

Podešavanja kolačića