Choose jour language!

---

|

DP: Fibonacci sa memoizacijom

1. Uvod

Fibonacci niz je najčešći početni primer za objašnjavanje dinamičkog programiranja.

Fibonaccijev niz je matematički niz brojeva u kome se svaki sledeći broj dobija kao zbir prethodna dva. Niz počinje sa 0 i 1, a zatim se nastavlja u beskonačnost. Prvih deset elemenata izgleda ovako:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Dužina niza zavisi od toga koji element n tražimo. Na primer, ako želimo da izračunamo F(7), to znači da se razmatra niz od prvih 8 elemenata (numerisano od 0 do 7):
n = 7 → niz ima 8 elemenata (od F(0) do F(7)).

Ovo daje intuitivnu sliku pre nego što pređemo na dinamičko programiranje: što je n veće, to je potrebno više računanja – posebno kod obične rekurzije. Pokazuje koliko se složenost može smanjiti prelaskom sa obične rekurzije na memoizaciju ili tabulaciju. U ovoj lekciji prikazujemo tri pristupa:

• Top-down (rekurzija + memoizacija)
• Bottom-up (tabulacija)
• Poređenje performansi

2. Definicija Fibonacci niza

Kada želimo da formalno opišemo Fibonacci niz, uvodimo funkciju F(n) koja za svako prirodno (ili celobrojno) n vraća n-ti Fibonacci broj. Uvođenje funkcije F nam omogućava da precizno izrazimo odnos između različitih članova niza — jer Fibonacci brojevi nisu nezavisni, već je svaki novi broj određen kombinacijom prethodnih. Drugim rečima, umesto da niz opisujemo rečima, funkcija F(n) nam daje matematički jasan i kratak način da zapišemo pravila koja generišu čitav niz.

Ova funkcija se definiše rekurzivno: osnovni slučajevi (baze) određuju početak niza, a svaka sledeća vrednost se dobija sabiranjem prethodna dva člana. To vodi do sledeće jednostavne, ali veoma moćne definicije:

F(0) = 0  
F(1) = 1  
F(n) = F(n−1) + F(n−2)

Za osnovno objašnjenje Fibonaccijevog niza i jednostavnu rekurzivnu verziju, pogledaj uvodnu stranu:
Fibonaccijev niz — uvodno objašnjenje

3. Naivna rekurzija (radi poređenja)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Ovaj pristup ima eksponencijalnu složenost O(2ⁿ), što ga čini vrlo sporim.

4. DP Top-down: Rekurzija + Memoizacija

Top-down pristup (rekurzija + memoizacija) znači da polazimo od krajnjeg problema — izračunavanja F(n) — i rekurzivno ga razbijamo na manje podprobleme (F(n−1), F(n−2), ...).

Međutim, za razliku od obične rekurzije koja ponavlja izračunavanja, top-down pamti rezultate podproblema u posebnoj tabeli (memo). Kada se kasnije ponovo zatraži isti podproblem, vrednost se odmah vraća iz tabele, bez ponovnog rekurzivnog poziva.

Ovakav pristup je intuitivan jer prati matematičku definiciju funkcije, ali smanjuje vreme sa eksponencijalnog na linearno.

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

// Memo tabela koja čuva ranije izračunate vrednosti.
// Koristimo long long jer Fibonacci brojevi veoma brzo rastu.
vector<long long> memo;

// Rekurzivna funkcija sa memoizacijom
long long fib_memo(int n) {

    // Baza rekurzije: F(0) = 0, F(1) = 1
    if (n <= 1)
        return n;

    // Ako je vrednost već izračunata — odmah je vraćamo.
    if (memo[n] != -1)
        return memo[n];

    // Inače izračunavamo rekurzivno i čuvamo dobijeni rezultat.
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);

    // Vraćamo zapamćenu vrednost.
    return memo[n];
}

int main() {
    int n;
    cout << "Unesite n: ";
    cin >> n;

    // Inicijalizujemo memo niz veličine n+1, sve vrednosti = -1
    // -1 znači da vrednost još nije izračunata.
    memo.assign(n + 1, -1);

    cout << "Fibonacci (Top-down) = " << fib_memo(n) << endl;
}

Prednosti

• Brz pristup – O(n)
• Prirodna rekurzivna logika

Mane

• Korišćenje rekurzije povećava potrošnju stack memorije

Napomena o memoriji za top-down (memoizacija)

Kod top-down (rekurzija + memoizacija) imamo dve glavne potrošnje memorije:

1. Heap/heap-like memorija za tabelu (memo) — niz u kojem čuvamo rezultate podproblema (npr. vector<long long> memo(n+1)).
2. Rekurzivni stack (call stack) — svaki rekurzivni poziv zauzima okvir (stack frame). Dubina steka je u najgorem slučaju jednaka broju nivoa rekurzije (za Fibonačijev primer to je ≈ n).

Kalkulacije i procene (kako brzo izračunati potrošnju)

1) Veličina memo niza
Ako koristiš long long (8 bajtova), memorija za memo je otprilike:

memory_memo ≈ (n + 1) * sizeof(long long)  // bajtovi

Primeri:

• n = 10⁴ → ≈ 80 000 B ≈ 0.08 MB
• n = 10⁵ → ≈ 800 000 B ≈ 0.8 MB
• n = 10⁶ → ≈ 8 000 000 B ≈ 8 MB

2) Procena stek-frame memorije
Veličina jednog rekurzivnog okvira (stack frame) značajno varira sa: kompajlerom, optimizacijama, brojem lokalnih promenljivih i parametrima funkcije. Zato dajemo procenu po tipu:

// aproksimacije (samо za procenu)
frame ≈ 32 – 128 bajtova (tipično)
stack_memory ≈ frame * depth  // bajtovi
depth ≈ maksimalna dubina rekurzije (za fib ≈ n)

Primeri (za frame = 64 B):

• n = 1 000 → stack ≈ 64 KB
• n = 10 000 → stack ≈ 640 KB
• n = 100 000 → stack ≈ 6.4 MB

Ograničenja operativnih sistema (praktičan rizik)

• Windows (default stack, glavna nit) često ima oko 1 MB stack-a po niti (može varirati). To znači da rekurzija dubine nekoliko hiljada može izazvati stack overflow na Windowsu.
• Linux (glibc) default obično ima 8 MB (može biti veće), pa podnosi veće dubine, ali i tu postoji granica (npr. za n ≈ 100 000 ćete najverovatnije probiti stek).
• Pored steka, ako je memo velik (n ≥ 10⁶ pri 8B po elementu → ≈ 8 MB), to takođe može dovesti do Memory Limit Exceeded (MLE) na platformama sa ograničenom memorijom.

Praktične preporuke

• Za N ≥ nekoliko hiljada — izbegavaj duboku rekurziju na Windowsu; koristi bottom-up (iterativno) rešenje.
• Ako ti treba memo table, izračunaj pre pokretanja koliko bajtova zauzima: size_bytes = (n+1) * sizeof(long long) i uporedi sa dostupnom memorijom (npr. 256 MB limit).
• Ako želiš održati top-down stil ali izbeći stack overflow — možeš:
  • povećati stack pri linkovanju (nije moguće na svim takmičarskim serverima),
  • prepraviti rekurziju u eksplicitnu stog-simulaciju koristeći vlastiti vector/stack (heap),
  • ili jednostavno implementirati bottom-up verziju koja ne koristi rekurziju.
• U takmičarskom kodu — uvek provere granice ulaza (n, maksimalne vrednosti) i uzmi najbezbedniji pristup (najčešće bottom-up ili 1D optimizacija) da izbegneš TLE/ MLE/ stack overflow.

Sažetak u tabeli (brza procena)

n	memo (≈ 8B po elementu)	stack (frame≈64B)	Napomena
10³	~8 KB	~64 KB	bez problema na većini sistema
10⁴	~80 KB	~640 KB	OK, ali Windows može biti blizu granice
10⁵	~0.8 MB	~6.4 MB	mogće MLE/stack na strogo ograničenim sistemima
10⁶	~8 MB	~64 MB	visok rizik od MLE/stack overflow

Kada DP nije primenljiv i zašto ne funkcioniše uvek?

Iako je problem Fibonaccija idealan primer za dinamičko programiranje, važno je razumeti da DP nije univerzalna tehnika i ne može se primeniti na svaku rekurziju. Da bi dinamičko programiranje imalo smisla, moraju biti ispunjena dva osnovna uslova:

• Optimalna podstruktura — rešenje problema može se dobiti kombinovanjem optimalnih rešenja njegovih manjih podproblema.
  Ako optimalno rešenje celog problema ne zavisi na jasan način od optimalnih rešenja podproblema, DP neće dati rezultat.
• Preklapanje podproblema — različiti rekurzivni putevi ponavljaju iste podprobleme više puta.
  Ako se podproblemi ne ponavljaju (npr. svaki rekurzivni poziv vodi ka potpuno novom stanju), tada memorisanje ne štedi vreme.

U slučaju Fibonaccija, oba uslova su ispunjena: svaki F(n) zavisi samo od F(n−1) i F(n−2), a ti podproblemi se ponavljaju mnogo puta, pa DP drastično ubrzava računanje.

Ali postoje problemi gde rekurzija postoji, ali DP ne pomaže: ako nema preklapanja podproblema (npr. obična binarna pretraga) ili nema optimalne podstrukture (npr. neki problemi sa globalnim ograničenjima).

Zbog toga je važno da učenici razumeju da DP nije „čarobni ubrzivač“, već metoda koja radi samo kada problem ima pravu strukturu. Fibonacci je dobar primer, ali ne treba stvoriti pogrešan utisak da je memoizacija primenljiva na svaku rekurziju.

Granični slučajevi i važna ograničenja

Iako memoizacija znatno ubrzava izračunavanje Fibonaccijevog niza, važno je pravilno obraditi granične slučajeve i razumeti ograničenja implementacije.

1. Granični slučajevi

• n = 0
  Funkcija treba da vrati 0. Ovo je validna vrednost i deo je standardne definicije Fibonaccijevog niza.
• n = 1
  Treba da vrati 1. Ovo se obično tretira kao bazni slučaj.
• n < 0
  Negativan Fibonaccijev indeks nema smisla u standardnoj definiciji. Preporuka:
  • vratiti grešku / exception
  • ili eksplicitno navesti u tekstu da je funkcija definisana samo za n ≥ 0

2. Ograničenja veličine n (memorija i vreme)

Top-down memoizacija koristi rekurziju i memo tabelu veličine O(n). To znači: ako je n veoma veliki, memorija i dubina steka postaju problem.

• n ≈ 10⁶: memo tabela zauzima oko 8 MB (ako koristiš long long), rekurzija može izazvati stack overflow.
• n ≈ 10⁷: memo tabela zahteva ~80 MB memorije → vrlo verovatno MLE (Memory Limit Exceeded). Rekurzija dubine 10⁷ je praktično nemoguća → siguran stack overflow.
• n > 10⁷: top-down pristup se ne može koristiti. Potrebne su alternativne metode (vidi dole).

3. Potencijalni overflow za long long

Tip long long (64-bitni) može da čuva vrednosti do otprilike 9.2 × 10¹⁸. To znači:

• F(92) je najveći Fibonacci broj koji staje u long long.
• F(93) i nadalje prelaze opseg → dolazi do overflow-a.

Ako radiš sa n većim od 92, rezultat sigurno neće stati u 64-bitni tip.

4. Šta koristiti za veoma velike n?

Ako se traži izračunavanje F(n) za n velik kao 10⁷, 10⁸, 10⁹ ili čak veći, onda memoizacija nije prikladna. Umesto toga koriste se efikasnije i stabilnije metode:

• Matrično stepenovanje: vreme O(log n), memorija konstantna. Koristi 2×2 matricu i brzo stepenovanje.
• Brzo stepenovanje zlatnim presekom (Binet formula) — nije preporučljivo zbog gubitka preciznosti kod velikih n.
• Modularni Fibonacci (kada se rezultat traži pod modom, npr. 10⁹+7).
• BigInteger / arbitrary precision (u Pythonu automatski, u C++ preko bibliotekа): omogućava izračunavanje F(n) za n stotine hiljada ili milione.
• Fast Doubling algoritam: najbrži i najprecizniji pristup za velike n. Radi u O(log n) vremenu i bez rekurzije velike dubine.

Ukratko: memoizacija je dobra za srednje n (do ~10⁵), ali nije za ekstremno velika n.

Ilustracija: broj poziva i dubina rekurzije — naivna rekurzija vs. memoizacija

Ovaj interaktivni blok pokazuje za dati n koliko funkcijskih poziva napravi naivna rekurzija (bez DP) i koliko poziva treba memoizovana verzija. Takođe prikazuje maksimalnu dubinu rekurzije (stack depth). Za mala n možeš videti i strukturu stabla poziva.

Unesi n: Prikaži rezultate Prikaži stablo poziva (samo za n ≤ 6)

Naivna rekurzija

Broj funkcijskih poziva: --

Maksimalna dubina rekurzije (stack): --

Napomena: naivna rekurzija ponavlja podprobleme eksponencijalno.

Top-down (memoizacija)

Broj funkcijskih poziva: --

Maksimalna dubina rekurzije (stack): --

Memoizacija izbegava ponovna računanja — svaki indeks se izračuna najviše jednom.

Stablo poziva (naivna rekurzija)

Stablo je prikaz svih rekurzivnih poziva. Vidljivo samo za male n.

---

Krátko objašnjenje (za nastavnike)

• Naivna rekurzija: broj poziva zadovoljava relaciju C(0)=1, C(1)=1, C(n)=1 + C(n-1) + C(n-2) ako brojimo i sam početni poziv. To raste ≈ φ^n.
• Memoizovana (top-down): svaki indeks 0..n se izračuna najviše jednom → broj poziva ≈ n+1 (za fib), a dubina stoga ≤ n.
• Ova razlika objašnjava zašto memoizacija prelazi sa eksponencijalnog na linearno vreme.

5. DP Bottom-up: Tabulacija

Bottom-up pristup (tabulacija) znači da gradimo rešenja podproblema iterativno od najmanjih ka većim. Za Fibonacci niz, to znači da prvo izračunamo F(0) i F(1), zatim F(2), F(3) itd., sve do F(n). Ovaj pristup ne koristi rekurziju, već direktno popunjava DP niz (tabelu) po redosledu, što izbegava duboke rekurzivne pozive.

Prednosti bottom-up pristupa:

• Nema rekurzije → nema opasnosti od stack overflow.
• Vreme izvršavanja je linearno O(n).
• Jasna iterativna logika → često jednostavnije za debug i razumevanje od top-down rekurzije.

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

long long fib_tab(int n) {
    if (n <= 1) return n;

    vector dp(n + 1);  // DP niz za čuvanje F(0)..F(n)
    dp[0] = 0;                     // baza
    dp[1] = 1;                     // baza

    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];  // DP prelaz: F(i) = F(i-1) + F(i-2)

    return dp[n];  // vrati traženi Fibonacci broj
}

int main() {
    int n;
    cout << "Unesite n: ";
    cin >> n;

    cout << "Fibonacci (Bottom-up) = " << fib_tab(n) << endl;
}

Prednosti

• Bez rekurzije
• O(n) vreme

Mane

• Korišćenje O(n) dodatne memorije

6. Optimalna Bottom-up verzija (O(1) memorija)

long long fib_opt(int n) {
    if (n <= 1) return n;

    long long a = 0, b = 1;  // čuvamo samo prethodna dva broja

    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;  // vrati F(n)
}

Prednosti

• O(1) memorija
• Najefikasniji pristup za velike n

Vizuelna tabela za Bottom-up tabulaciju

Donja tabela prikazuje kako se popunjava DP niz prilikom bottom-up izračunavanja Fibonaccijevih brojeva. Ovo pomaže da vizuelno razumeš kako algoritam postepeno gradi rešenja manjih podproblema.

Unesi n: Prikaži tabelu

---

Objašnjenje

• Svaki red predstavlja stanje posle jedne iteracije petlje.
• Plava ćelija označava indekse koji su upravo izračunati u toj iteraciji.
• Sve ostale ćelije prikazuju već izračunate vrednosti.
• Ovaj tip vizuelnog prikaza pomaže učenicima da shvate ključnu ideju dinamičkog programiranja: gradimo rešenja za veće indekse koristeći već rešene manje podproblome.

Alternativna rešenja: DP nije jedina optimizacija

Iako memoizacija značajno ubrzava Fibonacci računanje, postoje i druga, još efikasnija rešenja. Važno je da učenici shvate da dinamičko programiranje nije jedini način da se ubrza rekurzija.

1. Iterativno bottom-up rešenje sa samo 2 promenljive

Ovo je najjednostavnija i najefikasnija varijanta DP pristupa. Umesto niza ili tabele, čuvamo samo poslednja dva elementa:

long long fib(int n) {
    if (n <= 1) return n;

    long long a = 0;  // F(n-2)
    long long b = 1;  // F(n-1)

    for (int i = 2; i <= n; i++) {
        long long c = a + b;  // F(n)
        a = b;
        b = c;
    }

    return b;
}

Složenost: O(n) vreme, O(1) memorija. Ovo je praktično najbolje rešenje za većinu školskih i takmičarskih zadataka.

Ovo rešenje spada u bottom-up DP, jer koristi prethodno izračunate vrednosti podproblema, ali čuva samo poslednja dva broja radi optimizacije memorije. Dakle, princip dinamičkog programiranja ostaje, iako je prostor sveden na O(1).

2. Matrično stepenovanje – rešenje u O(log n)

Fibonacci niz može da se predstavi preko transformacione matrice:

| F(n+1) |   =   | 1 1 | × | F(n)   |
| F(n)   |       | 1 0 |   | F(n-1) |

Dakle: F(n) = (M^n)[1][0] gde je M osnovna Fibonacci matrica. Ako se koristi **binary exponentiation (brzo stepenovanje matrice)**, vreme postaje O(log n).

Ovo je korisno za veoma velika n (npr. 10¹⁵) uz mod aritmetiku.

2a. Matrično stepenovanje – implementacija u C++

Sledeći kod prikazuje kako se Fibonacci niz može izračunati korišćenjem 2×2 matrice i brzo stepenovanje (binary exponentiation). Vremenska složenost je O(log n).

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

// Množenje dve 2x2 matrice
void multiply(long long a[2][2], long long b[2][2]) {
    long long x = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    long long y = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    long long z = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    long long w = a[1][0]*b[0][1] + a[1][1]*b[1][1];

    a[0][0] = x;
    a[0][1] = y;
    a[1][0] = z;
    a[1][1] = w;
}

// Brzo stepenovanje matrice
void power(long long mat[2][2], long long n) {
    if(n <= 1) return;

    long long base[2][2] = {{1,1},{1,0}};
    power(mat, n/2);
    multiply(mat, mat);

    if(n % 2 != 0) multiply(mat, base);
}

// Fibonacci funkcija koristeći matricu
long long fib_matrix(long long n) {
    if(n == 0) return 0;
    long long mat[2][2] = {{1,1},{1,0}};
    power(mat, n-1);
    return mat[0][0];
}

int main() {
    long long n;
    cout << "Unesite n: ";
    cin >> n;

    cout << "Fibonacci (matrično) = " << fib_matrix(n) << endl;
}
  

Objašnjenje: - Matrica [[1,1],[1,0]] se koristi za transformaciju Fibonacci niza. - Funkcija power rekurzivno kvadrira matricu da bi dobila mat^n. - Ova metoda omogućava računanje veoma velikih F(n) bez duboke rekurzije ili velike memorije.

3. Fast Doubling — najefikasnija metoda za Fibonacci

Fast Doubling koristi identitete:

F(2k)   = F(k) × [2F(k+1) – F(k)]
F(2k+1) = F(k+1)² + F(k)²

Ova rekurzija takođe radi u O(log n) vremenu, ali je često brža i jednostavnija od matrica. Koristi se u većini ozbiljnih takmičarskih rešenja.

// Fast doubling (vraca par: F(n), F(n+1))
pair fib_fast(long long n) {
    if (n == 0) return {0, 1};

    auto p = fib_fast(n / 2);
    long long a = p.first;      // F(k)
    long long b = p.second;     // F(k+1)

    long long c = a * (2*b - a);        // F(2k)
    long long d = a*a + b*b;            // F(2k+1)

    if (n % 2 == 0) return {c, d};
    else return {d, c + d};
}

Ova metoda je preporučena za veoma velika n ili kada se traži računanje pod modulom.

Kada koristiti koju metodu?

• Memoizacija / DP: dobra za učenje, vizuelizaciju i srednje vrednosti n
• Iterativno O(1) rešenje: najbolje za klasične školske zadatke
• Matrično stepenovanje: dobro za vrlo velika n i mod aritmetiku
• Fast Doubling: najbrže i najčistije takmičarsko rešenje za velika n

Poenta je da postoje i brže metode od DP-a i da učenici upoznaju širi spektar algoritama.

7. Poređenje metoda

Metoda	Brzina	Memorija	Broj poziva
Naivna rekurzija	❌ Najsporija (O(2ⁿ))	Mala	Ogroman
Top-down (memoizacija)	✔ Brza (O(n))	Rekurzivni stack + niz	Srednje
Bottom-up	✔ Brza (O(n))	O(n)	Malo
Bottom-up O(1)	⭐ Najbrža	Minimalna	Najmanje

8. Zaključak

Dinamičko programiranje dramatično poboljšava efikasnost računanja Fibonacci brojeva. Top-down pristup je lak za razumevanje, dok je bottom-up (posebno O(1)) najefikasnija realna implementacija.

Skriveni mini kviz — Fibonacijev niz i memoizacija

Klikni da proveriš svoje znanje o Fibonacijevom nizu i DP pristupu sa memoizacijom!

Otvori kviz

Mini kviz: Da li razumeš DP primenu Fibonacijevog niza?

1. Koja je osnovna rekurzivna relacija za broj načina da se pređe stepenište?

ways(n) = ways(n-1) + ways(n-2)
ways(n) = ways(n-1) * ways(n-2)
ways(n) = n + ways(n-1)
Prikaži odgovor

2. Koja je početna vrednost za DP u top-down memoizaciji?

ways(0) = 1, ways(1) = 1
ways(0) = 0, ways(1) = 1
ways(0) = 1, ways(1) = 0
Prikaži odgovor

3. Koja je glavna prednost memoizacije u top-down pristupu?

Sprečava višestruko računanje istih podproblema
Skraćuje ulazni niz
Omogućava bottom-up popunjavanje
Prikaži odgovor

4. Zašto bottom-up verzija može biti stabilnija od top-down za velike N?

Jer izbegava duboku rekurziju i stack overflow
Jer koristi manje memorije za sve nizove
Jer računa samo prvu polovinu niza
Prikaži odgovor

5. Koja je vremenska složenost top-down rešenja sa memoizacijom?

O(2^N)
O(N)
O(log N)
Prikaži odgovor

6. Kako se može optimizovati bottom-up DP na O(1) memorije?

Čuvanjem samo poslednja dva izračunata broja
Čuvanjem celog DP niza
Korišćenjem top-down funkcije
Prikaži odgovor

□ Resetuj kviz

Primena Fibonaccija sa memoizacijom — zadatak za vežbu

Da bi se bolje razumela praktična primena memoizacije i dinamičkog programiranja, u nastavku se nalazi zadatak u kome se Fibonacci ne koristi samo kao niz, već kao deo algoritma koji rešava konkretan problem.

Zadatak: Broj načina da se pređe stepenište

Sportista želi da pređe stepenište koje ima N stepenika. U jednom koraku može da napravi:

• 1 korak, ili
• 2 koraka.

Potrebno je izračunati na koliko različitih načina sportista može da dođe do vrha stepeništa.

Primer:
Ako je N = 4, sportista može da dođe do vrha na način:

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2

Ukupno: 5 različitih načina.

Ideja za rešavanje (uputstvo — bez koda)

Ovaj problem je klasičan primer u kome se pojavljuje Fibonacci niz kao posledica strukture podproblema. Razmisli ovako:

• Da bi stigao do stepenika N, sportista je poslednji potez mogao biti:
  • sa stepenika N - 1 (napravio je 1 korak), ili
  • sa stepenika N - 2 (napravio je 2 koraka).

Dakle, broj načina da se dođe do stepenika N jednak je zbiru:

ways(N) = ways(N - 1) + ways(N - 2)

Ovo je identična rekurentna formula kao kod Fibonačijevog niza, samo sa malo drugačijim početnim vrednostima:

• ways(0) = 1 (jedan način: ne radimo ništa)
• ways(1) = 1 (jedan korak)

Kako rešiti zadatak efikasno?

Direktna rekurzija bi bila spora, jer bi se ista podproblem rešenja izračunavala više puta. Zbog toga treba koristiti memoizaciju:

• Kreiraj niz ili mapu za čuvanje već izračunatih rezultata.
• Ako je rezultat za N već izračunat → odmah ga vrati.
• Inače izračunaj rekurzivno i zapamti u memo tabeli.

Pokušaj samostalno da napraviš memoizovanu rekurziju (top-down) za ovaj problem. Rešenje treba da bude brzo čak i za N = 40 ili više.

Primena Fibonaccija sa memoizacijom — zadatak i rešenje

Zadatak: Broj načina da se pređe stepenište. Sportista želi da pređe stepenište od N stepenika. U jednom potezu može da napravi 1 ili 2 koraka. Potrebno je izračunati na koliko različitih načina može da stigne do vrha.

Primer: Ako je N = 4 — izlaz je 5.

Prikaži / sakrij uputstvo Prikaži / sakrij rešenje

Uputstvo — ideja rešenja

• Definiši ways(n) kao broj načina da se popne stepenište sa n stepenika (od 0 do n).
• Razmisli o poslednjem potezu: da bi stigao do n, poslednji potez je mogao biti sa n-1 (1 korak) ili sa n-2 (2 koraka).
• Zaključak: ways(n) = ways(n-1) + ways(n-2) — to je ista relacija kao Fibonacci niz.
• Početni uslovi: ways(0) = 1 (jedan način: ne pomerati se), ways(1) = 1.
• Direktna rekurzija je eksponencijalna jer ponavlja iste pozive. Rešenje: memoizacija (top-down) — čuvaj izračunate vrednosti u nizu (ili mapi) i vraćaj ih ako su već izračunate.

Plan implementacije (top-down)

1. Kreiraj vektor/niz memo dimenzije n+1 i inicijalizuj ga sa -1 (neizračunato).
2. Ako tražimo ways(k) i memo[k] != -1, vratiti memo[k].
3. Ako je k ≤ 1, vratiti 1 (baza).
4. Inače izračunati rekurzivno ways(k-1) i ways(k-2), sabrati i sačuvati u memo[k].

Bilješke o tipovima i ograničenjima

• Broj načina raste eksponencijalno ali za uobičajene zadatke (N ≤ 90) koristi se long long. Ako je N jako veliko, može biti potrebna rad sa modulom ili BigInteger.
• Top-down koristi rekurziju (dubina ≤ N). Ako je N veoma veliko, bottom-up iterativno rešenje izbegava dubinu stoga je stabilnije.

Rešenje — C++ (top-down memoizacija)

Objašnjenje pre koda:

• Kod koristi vektor memo tipa long long inicijalizovan sa -1.
• Funkcija ways vraća broj načina za dati k i koristi memoizaciju da bi izbegla ponovna računanja.
• Glavna funkcija učitava N, inicijalizuje memo i ispisuje rezultat.

Copy

// Broj nacina da se pređe stepenište — top-down (memoizacija)
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

vector<ll> memo;

// vraca broj nacina da se pređe stepenik k
ll ways(int k) {
    if (k <= 1) return 1;          // ways(0) = 1, ways(1) = 1
    if (memo[k] != -1) return memo[k];   // ako je vec racunato, vrati
    // memoizovani pozivi umesto ponovljenih rekurzija
    memo[k] = ways(k - 1) + ways(k - 2);
    return memo[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    // koristiti long long za sigurnu granicu; inicijalizujemo memo sa -1
    memo.assign(N + 1, -1);

    cout << ways(N) << '\n';
    return 0;
}
    

Analiza kompleksnosti

• Vreme: O(N) — svaki indeks od 0..N se izračuna najviše jednom.
• Memorija: O(N) za memo plus rekurzivni stack dubine O(N).

Alternativno rešenje — Bottom-up (iterativno)

Kratko: bottom-up verzija popunjava dp niz od 0 do N. Može se optimizovati na O(1) memorije koristeći samo dve promenljive.

// Bottom-up (tabulacija) + O(1) memorije
#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    if (N == 0) { cout << 1 << '\n'; return 0; }
    if (N == 1) { cout << 1 << '\n'; return 0; }

    ll a = 1; // ways(0)
    ll b = 1; // ways(1)
    for (int i = 2; i <= N; ++i) {
        ll c = a + b; // ways(i) = ways(i-1) + ways(i-2)
        a = b;
        b = c;
    }
    cout << b << '\n';
    return 0;
}
    

Komparativna napomena

• Top-down je često brže za implementaciju i lakše za razumevanje kod problema sa više parametara stanja.
• Bottom-up je bez rekurzije, obično koristi manje stack memorije i lako se optimizuje na O(1) prostora kad prelaz zavisi samo od konstantnog broja prethodnih stanja.

Test primer

Ulaz:
4

Izlaz:
5
    

Drugi zadatak za vežbu — Skakanje po brojevima

Ovaj zadatak dodatno vežba razumevanje rekurentnih odnosa i upotrebu memoizacije ili tabulacije kod problema sa preklapajućim podproblemima. Iako je jednostavan, veoma liči na probleme sa zvaničnih takmičenja.

Zadatak: Skakanje do cilja

Data je jedna linija brojeva (niz) dužine N, gde svaki element označava maksimalan broj polja koje možemo skočiti unapred sa te pozicije.

Počinješ na poziciji 0 (prvom elementu niza), i cilj je da stigneš do pozicije N - 1 (poslednjeg elementa).

Potrebno je izračunati:
Koliko različitih načina postoji da se dođe do poslednje pozicije?

Primer:

Ulaz:
N = 4
niz = [1, 2, 1, 1]

Značenje:
- sa pozicije 0 možeš skočiti najviše 1
- sa pozicije 1 možeš skočiti najviše 2
- sa pozicije 2 možeš skočiti najviše 1
- sa pozicije 3 možeš skočiti najviše 1

Mogući putevi:
0 → 1 → 2 → 3
0 → 1 → 3

Ukupno: 2 načina.

Ideja za rešavanje (uputstvo — bez koda)

Posmatraj problem kao usmereni graf: sa svake pozicije i možeš skočiti na pozicije i+1, i+2, ..., i + a[i] (ako ostaju u granicama niza).

Ako definišemo funkciju:

ways(i) = broj načina da se stigne od pozicije i do kraja

onda važi rekurentni odnos:

ways(i) = ways(i+1) + ways(i+2) + ... + ways(i + a[i])

Osnovni slučaj je jasan:

• ways(N - 1) = 1 — već si na kraju, postoji tačno jedan način

Kako rešiti efikasno?

Ovaj problem ima preklapanje podproblema: funkcije ways(i) se više puta ponovo pozivaju ako koristiš čistu rekurziju.

Zato koristi:

• memoizaciju (top-down): pre svakog rekurzivnog poziva proveri da li je rezultat već izračunat.
• tabulaciju (bottom-up): popuni DP niz od kraja ka početku.

Obrati pažnju da rezultat može brzo rasti — po potrebi koristi long long.

Preporučuje se da prvo uradiš top-down verziju, jer je intuitivnija, a zatim pređeš na bottom-up rešenje kao vežbu za dinamičko programiranje.

Rešenje zadatka — Skakanje po brojevima (DP sa memoizacijom)

U ovom delu nalazi se kompletno uputstvo i potpuno objašnjeno rešenje za zadatak „Skakanje do cilja“. Ideja je da se još jednom produbi razumevanje rekurentnih odnosa, memoizacije i tabulacije, koji spadaju u osnovne tehnike dinamičkog programiranja.

Prikaži / sakrij uputstvo Prikaži / sakrij rešenje

Uputstvo — ideja rešenja

Imamo niz a[] dužine N. Sa pozicije i možemo skočiti na bilo koju poziciju:

i + 1, i + 2, ..., i + a[i]

Sve dok ostajemo u granicama niza. Želimo da izračunamo:

ways(i) = broj načina da se stigne od pozicije i do kraja

Za svaku poziciju saberemo načine od svih mogućih skokova sa nje:

ways(i) = ways(i+1) + ways(i+2) + ... + ways(i + a[i])

Osnovni slučaj

• ways(N - 1) = 1 — ako smo već na poslednjoj poziciji, postoji tačno jedan način.

Zašto DP?

Kod obične rekurzije funkcije ways(i) se mnogo puta ponavljaju. Ako postoji puno malih skokova, grane se preklapaju. To daje eksponencijalnu složenost.

Zato koristimo:

• Memoizaciju (top-down) — čuvamo rezultat za svaku poziciju.
• Tabulaciju (bottom-up) — krećemo od kraja i popunjavamo DP tabelu unazad.

Plan za top-down memoizaciju

1. Kreirati vektor dp dimenzije N i popuniti ga sa -1.
2. Implementirati rekurzivnu funkciju ways(i).
3. Ako je dp[i] != -1, vratiti zapamćeni rezultat.
4. Ako je i == N - 1, vratiti 1.
5. Inače sabrati sve ways(i + k) za 1 ≤ k ≤ a[i] i zapamtiti rezultat.

Plan za bottom-up tabulaciju

1. Kreirati dp[] dužine N.
2. Postaviti dp[N - 1] = 1.
3. Od i = N-2 ka 0 izračunati:

dp[i] = dp[i+1] + dp[i+2] + ... + dp[i + a[i]]

Ovo daje isto rešenje, ali bez rekurzije.

Rešenje — C++ (top-down memoizacija)

Ovo je najintuitivnije rešenje, jer prati direktnu definiciju problema.
Komentari detaljno objašnjavaju šta se dešava u svakom koraku.

Copy

// Skakanje po brojevima — broj načina (top-down, memoizacija)
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
vector<ll> dp;
vector<int> a;
int N;

ll ways(int i) {
    if (i == N - 1) return 1;
    if (dp[i] != -1) return dp[i];
    ll sum = 0;
    for (int k = 1; k <= a[i]; k++) {
        int nxt = i + k;
        if (nxt < N) sum += ways(nxt);
    }
    dp[i] = sum;
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    dp.assign(N, -1);
    cout << ways(0) << "\n";
    return 0;
}
    

Objašnjenje koda

• dp[i] čuva rezultat za poziciju i.
• Ako dp[i] nije -1, rezultat je već izračunat.
• Sa pozicije i ispitujemo sve legalne skokove i sabiramo načine.
• Rekurzija ide sve dok ne dođe do N - 1.

Vremenska i memorijska složenost

• Vreme: O(N · K), gde je K prosečan broj mogućih skokova.
• Memorija: O(N) za dp + rekurzivni stack.

Vizuelna DP tabela (bottom-up tabulacija)

Ovo je ilustracija kako se popunjava DP tabela za primer:

N = 4
a = [1, 2, 1, 1]

Podsećanje:
dp[i] = broj načina da se dođe od pozicije i do kraja (pozicija N–1).

Korak po korak popunjavanje tabele

Pozicija i	a[i]	dp[i]	Objašnjenje
3	1	1	baza — poslednja pozicija
2	1	1	dp[2] = dp[3] = 1
1	2	2	dp[1] = dp[2] + dp[3] = 1 + 1 = 2
0	1	2	dp[0] = dp[1] = 2

Konačan rezultat

dp[0] = 2 Postoje tačno dva različita načina da se stigne do poslednje pozicije.

Kratko objašnjenje boja u tabeli

• a[i] — vrednosti skokova
• dp[i] — izračunati brojevi načina
• žuta — posebni ključni koraci (baza)

Izazovni zadatak (takmičarski nivo): Generalizovani Fibonacci

□ Zadatak: K-bonacci niz

Neka je dat ceo broj K (2 ≤ K ≤ 20) i ceo broj N (1 ≤ N ≤ 2000). Definišemo K-bonacci niz na sledeći način:

• Za prvih K elemenata važi: F[1] = F[2] = ... = F[K] = 1
• Za svaki sledeći element: F[n] = F[n-1] + F[n-2] + ... + F[n-K]

Zadatak je da izračunate F[N] mod 1 000 000 007.

✔ Ulaz

K N

✔ Izlaz

Jedan broj – vrednost F[N] mod 1e9+7.

---

□ Zašto je zadatak težak?

• Naivni pristup zahteva O(K·N) što je prihvatljivo samo za manje N.
• Brže rešenje koristi klizni prozor da bi sabiranja bila O(1).
• Za ogromne N neophodna je matrična eksponencijacija dimenzije K×K.

---

□ Smernice za DP rešenje

1. Kreirati niz dp dužine N i inicijalizovati dp[1…K] = 1.
2. Za svako n > K računati:

   dp[n] = (dp[n-1] + dp[n-2] + ... + dp[n-K]) % MOD

3. Za optimalno rešenje koristiti klizni prozor:

   window_sum = dp[1] + dp[2] + ... + dp[K]
   
   for n from K+1 to N:
       dp[n] = window_sum
       window_sum = window_sum + dp[n] - dp[n-K]

---

□ Očekivano znanje

• memoizacija i tabulacija
• klizni prozor nad DP nizom
• modularna aritmetika
• optimizacija memorije: O(N) → O(K)

---

Prethodno
​|< Uvod u dinamičko programiranje

Sledeće
DP: Problem ranca (Knapsack problem) >|

---