Choose your language!

---

|

Šta je Grid DP i zašto je važan?

Grid DP (dinamičko programiranje na mreži) predstavlja posebnu klasu problema u kojima radimo sa dvodimenzionalnom matricom (gridom) i želimo da izračunamo neku vrednost za svako polje na osnovu prethodno izračunatih polja.

Najčešći primer je sledeći:

• Data je matrica dimenzija n × m,
• nalazimo se u gornjem levom uglu,
• želimo da stignemo do donjeg desnog ugla,
• dozvoljeno je kretanje samo udesno ili nadole.

Pitanje koje se postavlja je: Na koliko različitih načina možemo stići do cilja?

Na prvi pogled, problem može delovati kombinatorno — ali broj mogućih puteva brzo postaje ogroman. Pokušaj da se generišu svi putevi bio bi prespor, jer broj kombinacija eksponencijalno raste.

Ovde dolazi do izražaja dinamičko programiranje. Umesto da ponavljamo ista računanja, koristimo činjenicu da se do svakog polja dolazi iz nekog prethodnog polja, pa rezultat možemo graditi postepeno.

Zašto je Grid DP važan u takmičenjima?

Grid DP problemi su izuzetno česti u takmičarskom programiranju i na prijemnim testovima za IT kompanije.

• Brojanje puteva kroz mrežu
• Minimalna suma puta
• Maksimalna vrednost prikupljenih poena
• Problemi sa preprekama
• Kretanje u više pravaca

Razumevanje ovog tipa problema pomaže da se lakše savladaju naprednije DP tehnike, jer uvodi rad sa dvodimenzionalnim stanjima.

Ako ste već učili 1D dinamičko programiranje (poput Fibonacci niza), Grid DP je prirodan sledeći korak — umesto jedne dimenzije, sada radimo sa dve.

Ovaj problem se često javlja u zadacima gde prelazimo kroz matricu koristeći srodne tehnike kao što su BFS (Breadth-First Search) za minimizaciju koraka. Za takve probleme, pogledajte sekciju BFS na gridu u lekciji o grafovima.

Za probleme koji se bave prelaskom kroz mrežu bez težina (npr. minimalan broj koraka) pogledajte i BFS na gridu, koji koristi pretragu grafa u matrici.

Opis osnovnog problema

Razmotrimo pravougaonu matricu dimenzija n × m. Polja su indeksirana od (0, 0) do (n−1, m−1).

Nalazimo se u polju (0, 0) — gornji levi ugao, a cilj nam je da stignemo do polja (n−1, m−1) — donji desni ugao.

Dozvoljena su samo sledeća kretanja:

• jedan korak udesno (i, j → i, j+1)
• jedan korak nadole (i, j → i+1, j)

Potrebno je odrediti na koliko različitih načina možemo stići od početnog do krajnjeg polja.

Zašto je naivno rešenje presporo?

Jedan pristup bi bio da rekurzivno generišemo sve moguće puteve. Međutim, broj puteva brzo raste kako se dimenzije matrice povećavaju.

Na primer, već za matricu 20 × 20 broj puteva je veoma veliki, pa bi generisanje svih kombinacija bilo izuzetno sporo.

Zbog toga koristimo dinamičko programiranje — umesto da ponavljamo ista računanja, čuvamo rezultate za svako polje.

Definicija DP stanja

Definišemo dvodimenzionalni niz:

• dp[i][j] predstavlja broj različitih puteva kojima možemo stići do polja (i, j).

Ovo znači da za svako polje želimo da znamo koliko različitih načina postoji da do njega dođemo koristeći dozvoljena kretanja.

Naš konačni cilj je da izračunamo vrednost:

• dp[n-1][m-1]

što predstavlja ukupan broj različitih puteva do cilja.

DP prelaz (relacija)

Da bismo izračunali vrednost dp[i][j], postavimo pitanje: Odakle možemo doći u polje (i, j)?

Pošto su dozvoljena samo dva kretanja — udesno i nadole — u polje (i, j) možemo stići:

• iz polja iznad: (i-1, j)
• iz polja levo: (i, j-1)

Ako znamo broj puteva do tih polja, onda je ukupan broj puteva do polja (i, j) jednak zbiru ta dva broja.

Dakle, dobijamo osnovnu DP relaciju:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

Početni uslovi

Da bi relacija radila ispravno, moramo definisati početne vrednosti.

• dp[0][0] = 1

  — postoji tačno jedan način da budemo na početnom polju.

Za prvu vrstu (i = 0):

• Možemo se kretati samo udesno, pa je svaki element jednak 1.

Za prvu kolonu (j = 0):

• Možemo se kretati samo nadole, pa je svaki element takođe jednak 1.

Time smo definisali sve potrebne uslove za popunjavanje cele DP tabele.

Implementacija u C++ (sa objašnjenjima)

U ovom programu rešavamo klasičan Grid DP problem: želimo da iz gornjeg levog ugla matrice dimenzija n × m stignemo do donjeg desnog ugla, krećući se samo udesno ili nadole.

Formiramo DP tabelu dimenzija n × m, gde:

• dp[i][j] predstavlja broj različitih puteva do polja (i, j),
• u svako polje možemo doći ili iz polja iznad (i−1, j),
• ili iz polja levo (i, j−1).

Zbog toga važi sledeća relacija:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

Početno stanje:

• dp[0][0] = 1 — postoji tačno jedan način da budemo na početnom polju.

Konačan odgovor je vrednost dp[n-1][m-1], odnosno broj načina da stignemo do donjeg desnog ugla.

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

int main() {
    int n, m;
    cin >> n >> m;  
    // n = broj redova
    // m = broj kolona

    // Kreiramo DP tabelu n x m
    // dp[i][j] = broj načina da dođemo do polja (i, j)
    vector<vector<int>> dp(n, vector<int>(m, 0));

    // Početno polje
    dp[0][0] = 1;

    // Popunjavanje DP tabele
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            // Ako možemo doći odozgo
            if (i > 0)
                dp[i][j] += dp[i-1][j];

            // Ako možemo doći sleva
            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }

    // Konačan odgovor
    cout << dp[n-1][m-1];
}

Grid sa preprekama

Često se u zadacima neka polja ne mogu koristiti (predstavljaju prepreke). U tom slučaju:

• Ako je polje prepreka → dp[i][j] = 0
• Inače koristimo istu relaciju kao ranije

Pre nego što računamo vrednost za polje, proveravamo da li je ono dozvoljeno. Ako je početno polje prepreka — rezultat je 0.

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // Učitavanje matrice
    // 0 = slobodno polje
    // 1 = prepreka
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    if (grid[0][0] == 0)
        dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            if (grid[i][j] == 1) {
                dp[i][j] = 0; // prepreka
                continue;
            }

            if (i > 0)
                dp[i][j] += dp[i-1][j];

            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[n-1][m-1];
}

Složenost algoritma

• Vremenska složenost: O(n × m)
• Prostorna složenost: O(n × m)

Pošto svako polje računamo tačno jednom, algoritam je veoma efikasan i pogodan za matrice srednje veličine (n, m do nekoliko hiljada).

Optimizacija memorije

Pošto nam je za računanje potrebna samo trenutna i prethodna vrsta, možemo smanjiti memoriju sa O(n × m) na O(m).

To je česta tehnika u takmičenjima kada su ograničenja velika.

Primer popunjavanja DP tabele

Razmotrimo jednostavan primer matrice dimenzija 3 × 3. Želimo da izračunamo broj puteva od (0,0) do (2,2).

Na početku postavljamo:

• dp[0][0] = 1
• Prva vrsta = 1 (kretanje samo udesno)
• Prva kolona = 1 (kretanje samo nadole)

1	1	1
1	?	?
1	?	?

Sada računamo ostala polja koristeći relaciju:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Polje (1,1):

• Dolazimo iz (0,1) = 1
• Dolazimo iz (1,0) = 1

Zato je:

dp[1][1] = 1 + 1 = 2

1	1	1
1	2	?
1	?	?

Polje (1,2):

• Dolazimo iz (0,2) = 1
• Dolazimo iz (1,1) = 2

dp[1][2] = 1 + 2 = 3

Polje (2,1):

• Dolazimo iz (1,1) = 2
• Dolazimo iz (2,0) = 1

dp[2][1] = 2 + 1 = 3

Na kraju, polje (2,2):

• Dolazimo iz (1,2) = 3
• Dolazimo iz (2,1) = 3

dp[2][2] = 3 + 3 = 6

1	1	1
1	2	3
1	3	6

Dakle, postoji 6 različitih puteva od gornjeg levog do donjeg desnog ugla u mreži 3 × 3.

Na ovom primeru jasno vidimo kako se tabela gradi postepeno — svako polje zavisi samo od već izračunatih suseda.

Implementacija (C++)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    long long dp[n][m];

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i == 0 && j == 0)
                dp[i][j] = 1;
            else {
                long long fromUp = (i > 0) ? dp[i-1][j] : 0;
                long long fromLeft = (j > 0) ? dp[i][j-1] : 0;
                dp[i][j] = fromUp + fromLeft;
            }
        }
    }

    cout << "Broj puteva: " << dp[n-1][m-1];
    return 0;
}

---

Grid sa preprekama

Često neka polja ne mogu da se koriste (prepreke). Takva polja obeležimo, na primer, sa 1, dok su slobodna polja 0.

Ako je polje prepreka, tada:

dp[i][j] = 0

---

Primer: grid sa preprekama (C++)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int grid[n][m];
    long long dp[n][m];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> grid[i][j];

    if(grid[0][0] == 1) {
        cout << 0;
        return 0;
    }

    dp[0][0] = 1;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                if(i == 0 && j == 0) continue;
                long long fromUp = (i > 0) ? dp[i-1][j] : 0;
                long long fromLeft = (j > 0) ? dp[i][j-1] : 0;
                dp[i][j] = fromUp + fromLeft;
            }
        }
    }

    cout << dp[n-1][m-1];
    return 0;
}

Složenost algoritma

Analizirajmo efikasnost našeg rešenja.

Vremenska složenost

DP tabelu dimenzija n × m popunjavamo tako što svako polje računamo tačno jednom.

Za svako polje radimo konstantan broj operacija (zbir dve vrednosti).

Zbog toga je ukupna vremenska složenost:

• O(n × m)

Ovo je veoma efikasno rešenje, jer je svako stanje izračunato samo jednom.

Prostorna složenost

Koristimo dvodimenzionalnu tabelu veličine n × m, pa je memorijska složenost:

• O(n × m)

Za matrice srednje veličine (n i m do nekoliko hiljada) ovo je potpuno prihvatljivo.

Kada može doći do problema?

• Ako su dimenzije veoma velike (npr. 10⁵ × 10⁵), memorija postaje problem.
• Ako je broj puteva veoma veliki, može doći do prekoračenja opsega tipa int.

U takvim situacijama koristimo:

• long long tip promenljive
• računanje rezultata modulo nekog broja (npr. 10⁹ + 7)
• optimizaciju memorije na O(m)

Time Grid DP postaje primenljiv i za znatno veće ulaze.

Varijanta: Minimalna suma puta

U ovoj verziji problema, svako polje matrice sadrži neku vrednost (cenu).

Cilj više nije da brojimo puteve, već da pronađemo minimalnu moguću sumu vrednosti polja kroz koja prolazimo od (0,0) do (n−1,m−1).

Dozvoljena kretanja su i dalje:

• udesno
• nadole

Definicija DP stanja

• dp[i][j] predstavlja minimalnu sumu potrebnu da stignemo do polja (i, j).

DP relacija

Pošto do polja (i, j) možemo doći iz polja iznad ili sleva, biramo onaj put koji daje manju sumu:

• dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Početni uslovi

• dp[0][0] = grid[0][0]
• Prva vrsta se puni sabiranjem s leva
• Prva kolona se puni sabiranjem odozgo

Implementacija u C++

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m));

    // Učitavanje matrice
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dp[0][0] = grid[0][0];

    // Popunjavanje prve vrste
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    // Popunjavanje prve kolone
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    // Popunjavanje ostatka tabele
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    cout << dp[n-1][m-1];
}

Ovde vidimo kako se struktura problema ne menja — menja se samo operacija:

• kod brojanja → sabiranje
• kod optimizacije → minimum (ili maksimum)

Ovo pokazuje koliko je Grid DP fleksibilna i moćna tehnika.

Varijanta: Grid sa preprekama

U ovoj verziji problema, neka polja matrice predstavljaju prepreke koje nije moguće koristiti.

Cilj je i dalje da stignemo od polja (0,0) do (n-1,m-1), ali sada treba izbeći blokirana polja.

Predstavljamo prepreke numerički:

• 0 → slobodno polje
• 1 → polje sa preprekom

Definicija DP stanja

• dp[i][j] predstavlja broj puteva do polja (i,j) koji ne prolaze kroz prepreke.

DP relacija

Ako je polje (i,j) slobodno:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

Ako je polje prepreka:

• dp[i][j] = 0

Početno polje (0,0) se postavlja na 1 samo ako nije prepreka.

Implementacija u C++

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // Učitavanje matrice
    // 0 = slobodno polje, 1 = prepreka
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    if (grid[0][0] == 0)
        dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0; // prepreka
                continue;
            }
            if (i > 0)
                dp[i][j] += dp[i-1][j];
            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[n-1][m-1];
}

Ovaj primer pokazuje koliko je osnovna struktura DP tabele fleksibilna: menja se samo uslov za prepreke, dok relacija ostaje ista.

Varijanta: Maksimalna suma puta

U ovoj verziji, svako polje matrice sadrži neku vrednost. Cilj je da pronađemo put sa maksimalnom sumom vrednosti od (0,0) do (n−1,m−1), krećući se samo udesno ili nadole.

Ova varijanta je slična Minimalnoj sumi puta, samo što sada biramo maksimum umesto minimuma.

Definicija DP stanja

• dp[i][j] predstavlja maksimalnu sumu koju možemo prikupiti do polja (i,j).

DP relacija

Za svako polje (i,j), možemo doći iz polja iznad ili sleva:

• dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Početni uslovi:

• dp[0][0] = grid[0][0]
• Prva vrsta se puni sabiranjem s leva
• Prva kolona se puni sabiranjem odozgo

Implementacija u C++

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m));

    // Učitavanje matrice
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dp[0][0] = grid[0][0];

    // Popunjavanje prve vrste
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    // Popunjavanje prve kolone
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    // Popunjavanje ostatka tabele
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    cout << dp[n-1][m-1];
}

Ova varijanta pokazuje da ista struktura DP tabele može da reši različite zadatke samo promenom operacije (sabiranje → minimum/maksimum, ili brojanje).

Napomene za takmičenja i granični slučajevi

Kada rešavate Grid DP probleme na takmičenjima ili u vežbama, važno je obratiti pažnju na nekoliko praktičnih detalja.

1. Tip promenljive

• Broj puteva može brzo postati veoma veliki.
• Koristite long long umesto int kada broj prelazi ~10⁹.
• Ako je zadatak modulovan (npr. 10⁹ + 7), računate modulo nakon svakog sabiranja.

2. Početno polje može biti blokirano

• Ako je dp[0][0] prepreka, rezultat je odmah 0.
• Slično važi i ako je cilj blokiran — nema rešenja.

3. Dimenzije matrice

• Za vrlo velike matrice (n, m > 10⁴) dvodimenzionalna tabela može zauzeti previše memorije.
• U tim slučajevima koristite optimizaciju memorije: čuvajte samo prethodni red (O(m) prostora).

4. Granični slučajevi

• Jedna vrsta ili jedna kolona — DP se svodi na jednostavno sabiranje.
• Negativne vrednosti u matrici — minimalna ili maksimalna suma puta može zahtevati pažljivo postavljanje početnih uslova.
• Prepreke na rubovima matrice — proveriti DP relaciju da ne dolazi do pristupa van opsega.

5. Saveti za takmičare

• Prvo rešite osnovni problem bez prepreka, da razumete popunjavanje tabele.
• Zatim dodajte prepreke i optimizaciju suma.
• Uvijek testirajte male primere ručno kako biste proverili logiku.

Napredna varijanta: Putanja sa minimalnim ukupnim pomeranjem

U ovoj verziji problema, svako polje matrice sadrži broj neistomišljenika. Domski Sletač želi da pronađe putanju od polja (0,0) do (n−1,m−1), krećući se samo:

• udesno
• nadole

Za razliku od klasičnih grid DP zadataka, cilj nije da minimizujemo zbir vrednosti na samoj putanji, već:

ukupnu udaljenost koju će svi neistomišljenici preći do najbližeg polja na izabranoj putanji.

Zašto običan DP nije dovoljan?

Kod standardnih zadataka često koristimo formulu:

dp[i][j] =
    min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

Ovde to nije moguće primeniti direktno.

Razlog je što vrednost grid[i][j] nije unapred poznata. Cena nekog polja ne zavisi samo od tog polja, već od:

• svih neistomišljenika u matrici
• njihove udaljenosti do putanje
• načina na koji se putanja prostire kroz matricu

Zbog toga moramo promeniti način razmišljanja.

Ključna ideja

Umesto da posmatramo problem ovako:

• „svaki neistomišljenik traži najbliže polje na putanji“

mnogo je lakše razmišljati ovako:

• „putanja se postepeno širi kroz matricu“

Kada putanja stigne do novog polja:

• dodaje se novi deo reda ili kolone
• deo neistomišljenika tada prvi put dolazi do putanje
• njihov doprinos ukupnoj ceni tada se računa tačno jednom

Na taj način dobijamo mogućnost da koristimo dinamičko programiranje.

Kako se putanja „širi“?

Ako do polja (i,j) dolazimo:

• odozgo → dodajemo novi deo trenutnog reda
• sleva → dodajemo novi deo trenutne kolone

Važno je primetiti:

• ne obrađujemo celu matricu svaki put ❌
• već samo „novi sloj“ koji je upravo dodat ✔

Šta predstavlja DP stanje?

Koristimo standardnu grid DP ideju:

dp[i][j]

predstavlja:

• minimalnu ukupnu cenu za neku putanju koja stiže do polja (i,j)

Prelaz ostaje sličan kao kod običnog grid DP-a:

dp[i][j] =
    min(
        dp[i-1][j] + cena_dolaska_odozgo,
        dp[i][j-1] + cena_dolaska_sleva
    );

Razlika je u tome što:

• „cena“ nije unapred data
• već je moramo efikasno izračunati

Naivna ideja — i problem

Pretpostavimo da dolazimo odozgo u polje (i,j).

Tada moramo dodati doprinos svih polja:

(i,1), (i,2), ..., (i,j-1)

Svako od tih polja mora da se pomeri udesno do kolone j.

Naivan pristup bio bi:

for (k = 1; k < j; k++)
    suma += a[i][k] * (j - k);

Ali ako ovo radimo za svako polje matrice:

• složenost postaje prevelika ❌

Optimizacija pomoću prefiksnih suma

Umesto obilaska svakog polja posebno, koristimo:

• prefiksne sume

Pamtićemo:

• običan zbir elemenata
• ponderisan zbir elemenata

Na primer:

sum a[i][k] * (j - k)
=
j * sum(a[i][k]) - sum(a[i][k] * k)

Na taj način:

• ceo zbir računamo u O(1)
• bez prolaska kroz sva polja

Šta predstavljaju promenljive k i r?

U formulama se često pojavljuju promenljive:

• k — tekuća kolona u redu
• r — tekući red u koloni

Na primer:

sum a[i][k] * (j - k)

znači:

• prolazimo kroz sve kolone k levo od j
• svako polje mora da pređe (j-k) koraka udesno

Slično:

sum a[r][j] * (i - r)

• prolazimo kroz sve redove r iznad i
• svako polje mora da pređe (i-r) koraka nadole

Zašto ovo radi?

Ključna osobina zadatka je:

• neistomišljenici takođe smeju da se kreću samo: udesno ili nadole

Zbog toga:

• svako polje „pripada“ tačno jednom trenutku kada ga putanja prvi put dodirne
• nijedan doprinos se ne računa više puta

Upravo to omogućava efikasan DP pristup.

Dileme koje se često javljaju

• ❓ Da li treba pamtiti koja su polja već obrađena?
  ✔ Ne — to je implicitno određeno DP stanjem.
• ❓ Da li svaki put prolazimo kroz celu kolonu ili red?
  ✔ Ne — koristimo prefiksne sume i dobijamo rezultat u O(1).
• ❓ Da li se isti neistomišljenik računa više puta?
  ✔ Ne — svaki doprinos se dodaje tačno jednom.
• ❓ Da li bi isti pristup radio da je dozvoljeno kretanje i ulevo ili nagore?
  ✔ Ne nužno — tada više ne bismo imali jednostavno „širenje“ putanje.

Zaključak

Ovaj zadatak predstavlja odličan primer kombinovanja:

• dinamičkog programiranja
• prefiksnih suma
• pažljivog modelovanja problema

Najvažnija ideja nije sama DP formula, već:

da pravilno odredimo šta predstavlja novi doprinos kada se putanja proširi.

Kada se problem pravilno modeluje:

• skupa računanja nestaju
• a složen zadatak postaje standardan DP sa optimizacijama ✔

Vizuelna intuicija — kako se putanja „širi“

Najvažnija ideja u ovom zadatku je da se putanja ne posmatra odjednom, već kao proces koji se postepeno širi kroz matricu.

Kada putanja stigne u novo polje:

• dodaje se novi deo reda ili kolone
• samo ta nova polja prvi put dolaze u kontakt sa putanjom
• njihov doprinos ukupnoj ceni tada računamo

Dolazak odozgo

Pretpostavimo da dolazimo iz polja (i-1,j) u polje (i,j).

Na primer:

• i = 4
• j = 3

Dakle, dolazimo u polje:

(4,3)

Putanja tada prvi put dodiruje deo četvrtog reda.

X	X	X	X
X	X	X	X
X	X	X	X
?	?	(i,j) (4,3)	.

Legenda:

• X = već obrađena polja
• ? = nova polja koja sada prvi put ulaze u obračun
• (i,j) = trenutno polje u koje DP dolazi

Kada dolazimo odozgo:

• dodaje se novi deo reda
• konkretno polja: (i,1), (i,2), ..., (i,j)

Za primer iznad to su:

(4,1), (4,2), (4,3)

Svi neistomišljenici iz tih polja moraju da se pomere udesno do kolone j.

Ako se neko nalazi u polju:

(i,k)

onda prelazi:

j - k

koraka.

Šta predstavlja promenljiva k?

Promenljiva k predstavlja:

• tekuću kolonu unutar trenutnog reda

Naivan pristup bio bi:

for(int k = 1; k < j; k++) {
    suma += a[i][k] * (j - k);
}

Dakle:

• obilazimo sva polja levo od kolone j
• i sabiramo njihov doprinos

Ali to bi bilo presporo.

Zato koristimo prefiksne sume i formulu:

∑ a[i][k] * (j-k)
=
j * ∑a[i][k] - ∑(a[i][k] * k)

Dolazak sleva

Sada pretpostavimo da dolazimo iz:

(i,j-1)

u polje:

(i,j)

Na primer:

• i = 4
• j = 4

X	X	X	?
X	X	X	?
X	X	X	?
X	X	X	(i,j) (4,4)

Ovde dodajemo novu kolonu:

(1,j), (2,j), ..., (i,j)

Za primer iznad:

(1,4), (2,4), (3,4), (4,4)

Neistomišljenici sada moraju da se pomere nadole do reda i.

Ako se neko nalazi u:

(r,j)

onda prelazi:

i - r

koraka.

Šta predstavlja promenljiva r?

Promenljiva r predstavlja:

• tekući red unutar trenutne kolone

Naivan pristup bio bi:

for(int r = 1; r < i; r++) {
    suma += a[r][j] * (i - r);
}

Ali i ovo bi bilo presporo za velike matrice.

Zato koristimo:

∑ a[r][j] * (i-r)
=
i * ∑a[r][j] - ∑(a[r][j] * r)

Zašto je sve ovo važno?

• svaki doprinos računamo tačno jednom ✔
• ne obilazimo celu matricu pri svakom koraku ✔
• DP ostaje efikasan ✔
• prefiksne sume omogućavaju računanje u O(1) ✔

Interaktivni primer — prefiksne sume i K×K kvadrat

Sledeći primer prikazuje kako funkcionišu prefiksne sume u matrici.

Pređi mišem preko ćelije tabele da vidiš:

• vrednost prefiksne sume za to polje
• zbir K×K kvadrata koji se završava u toj ćeliji (ako postoji)

Šta predstavlja svaka ćelija?

Svaka ćelija prikazuje:

prefix[i][j]

odnosno zbir svih elemenata:

(0,0) → (i,j)

Na primer:

prefix[2][2]

sadrži zbir svih elemenata unutar regiona:

X X X
X X X
X X X

Kako dobijamo zbir K×K kvadrata?

Kada želimo zbir nekog regiona:

• ne prolazimo kroz sva polja kvadrata ❌
• već koristimo već izračunate prefiksne vrednosti ✔

Formula:

sum =
prefix[i][j]
- prefix[i-K][j]
- prefix[i][j-K]
+ prefix[i-K][j-K]

Na ovaj način:

• svaki zbir dobijamo u O(1)
• bez dodatnih petlji

Šta treba da primetiš?

• Prefiksne sume pamte informacije o prethodnim poljima ✔
• Veliki regioni mogu da se računaju veoma brzo ✔
• Umesto ponovnog sabiranja, koristimo već pripremljene rezultate ✔

Povezivanje sa glavnim zadatkom

U zadatku sa Domskim Sletačem:

• ne računamo samo običan zbir
• već zbir ponderisan udaljenošću

Ali osnovna ideja ostaje ista:

• izbegavamo prolazak kroz veliki broj polja
• koristimo unapred pripremljene sume
• dobijamo rezultat u konstantnom vremenu

Ključna intuicija

Prefiksne sume možeš posmatrati kao:

• „memoriju matrice“

One unapred pamte:

• zbirove prethodnih regiona
• kako kasnije ne bismo morali ponovo da obilazimo ista polja

Zadaci za vežbu — dinamičko programiranje u mreži

Zadatak 1: Brojanje puteva u mreži 3×3

Data je mreža dimenzija 3 × 3. Dozvoljena su kretanja samo udesno i nadole. Odredi koliko različitih puteva vodi od gornjeg levog do donjeg desnog ugla.

Prikaži / sakrij uputstvo

Uputstvo — brojenje puteva

Napravi DP tabelu dimenzija 3×3. Svako polje dp[i][j] predstavlja broj puteva do tog polja. Formula:

dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[0][0] = 1
    

Popuni prvu vrstu i prvu kolonu sa 1.

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

Broj puteva za 3×3 mrežu:

1 1 1
1 2 3
1 3 6
    

Odgovor: 6 puteva

Zadatak 2: Minimalna suma puta 4×4

Data je matrica dimenzija 4 × 4:

• {2, 3, 1, 4}
• {5, 6, 2, 1}
• {1, 2, 7, 3}
• {4, 3, 2, 1}

Odredi minimalnu sumu puta od gornjeg levog do donjeg desnog ugla. Kretanja: desno i dole.

Prikaži / sakrij uputstvo

DP tabela dimenzija 4×4:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    

Popuni prvu vrstu i prvu kolonu sabiranjem prethodnih vrednosti.

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

Popunjena DP tabela:

2  5  6 10
7 11  8  9
8 10 15 12
12 13 14 13
    

Minimalna suma puta = 13

Zadatak 3: Grid sa preprekama 5×5

Data je matrica dimenzija 5 × 5, gde 0 označava slobodno polje, a 1 prepreku. Kretanja: desno i dole.

0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
1 0 1 0 0
0 0 0 0 0
  

Prikaži / sakrij uputstvo

DP tabela dimenzija 5×5. Polje sa preprekom = 0, ostala polja = suma gornjeg i levog. Prva vrsta i kolona: 1 ako nema prepreke.

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

Popunjena DP tabela (0 = prepreka):

1 1 1 1 1
1 0 1 0 1
1 1 2 2 3
0 1 0 2 5
1 2 2 4 9
    

Broj puteva od gornjeg levog do donjeg desnog ugla = 9

Dodatni zadaci za vežbu (napredni)

Zadatak 4: Maksimalna suma puta 4×4

Data je matrica dimenzija 4 × 4 sa vrednostima polja:

• {1, 2, 3, 4}
• {2, 1, 4, 3}
• {3, 2, 1, 2}
• {4, 3, 2, 1}

Odredi maksimalnu sumu puta od gornjeg levog do donjeg desnog ugla. Dozvoljena kretanja: desno i dole.

Uputstvo (kratko):

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
  

Prikaži / sakrij uputstvo

Popuni prvu vrstu i prvu kolonu sabiranjem. Ostala polja računaj maksimum između gornjeg i levog polja plus trenutno polje. Na kraju, dp[n-1][m-1] je odgovor.

□ Savet: Probaj prvo ručno popuniti tabelu za malu matricu da vidiš kako maksimum raste.

Zadatak 5: Maksimalna suma puta sa preprekama 5×5

Data je matrica dimenzija 5 × 5, gde -1 označava prepreku (ne može se proći), a ostala polja sadrže vrednosti. Dozvoljena kretanja: desno i dole.

0   2   3   4   1
2  -1   1   5   2
3   2  -1   1   3
1   4   2   2   1
2   1   3   1   2
  

Uputstvo (kratko):

dp[i][j] = 0               if grid[i][j] == -1
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])  otherwise
  

Prikaži / sakrij uputstvo

Za prepreke staviti dp[i][j] = 0 ili neku markicu da se ne računa. Ostala polja računati maksimum između gornjeg i levog polja plus vrednost trenutnog polja.

□ Savet: Ako početno ili krajnje polje ima prepreku, rezultat je odmah 0.

Zadatak 6: Takmičarska varijanta — Veliki Grid sa modulom

Data je matrica dimenzija 1000 × 1000 sa vrednostima polja od 0 do 1000. Cilj: pronaći broj puteva od (0,0) do (999,999) takav da je zbir vrednosti polja maksimalan, a rezultat izračunati mod 1e9+7. Dozvoljena kretanja: desno i dole.

Uputstvo (kratko):

Koristi DP tabelu dp[i][j] = maksimalna suma puta do polja (i,j)
Ako suma prelazi 1e9+7, koristi dp[i][j] % 1e9+7
Za memorijsku optimizaciju možeš čuvati samo prethodni red (O(m) prostora)
  

Prikaži / sakrij uputstvo

Ovo je tipičan takmičarski zadatak gde je potrebno:

• Računati maksimalnu sumu puta
• Koristiti modul za izbegavanje prekoračenja
• Optimovati memoriju (čuvati samo prethodni red)

□ Savet: Počni sa manjim gridom da testiraš logiku pre nego što kreneš sa 1000×1000.

Šablon za proveru rešenja — Zadaci 4–6

Zadatak 4 & 5 — Maksimalna suma puta (male matrice)

Možete koristiti ovaj šablon da proverite svoje DP tabele za manje matrice (4×4 ili 5×5).

Prikaži / sakrij uputstvo

1) Napravite DP tabelu iste dimenzije kao matrica.
2) Popunjavajte po pravilima: dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1]) ili dp[i][j] = 0 ako je prepreka.
3) Početno polje: dp[0][0] = grid[0][0] ako nije prepreka.
4) Na kraju dp[n-1][m-1] daje maksimalnu sumu puta.

Provera DP tabele — C++ šablon

Copy

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dp[0][0] = grid[0][0];

    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (grid[i][j] == -1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    cout << dp[n-1][m-1] << '\n';
}
  

Zadatak 6 — Takmičarska varijanta (veliki grid + modul)

Za veći grid (n, m ≤ 1000) i brojanje modulo 1e9+7 koristite sledeći šablon:

Prikaži / sakrij uputstvo

1) Čuvajte samo prethodni red DP tabele (O(m) memorije).
2) Računajte dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j].
3) Nakon svake operacije koristite % MOD ako je potrebno.
4) Početno polje: dp[0][0] = grid[0][0].

Šablon — C++ (veliki grid)

Copy

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

const int MOD = 1e9+7;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> grid[i][j];

    vector<int> prev(m, 0), curr(m, 0);

    prev[0] = grid[0][0];

    for(int j=1;j<m;j++)
        prev[j] = prev[j-1] + grid[0][j];

    for(int i=1;i<n;i++){
        curr[0] = prev[0] + grid[i][0];
        for(int j=1;j<m;j++){
            curr[j] = max(prev[j], curr[j-1]) + grid[i][j];
            if(curr[j] >= MOD) curr[j] %= MOD;
        }
        prev = curr;
    }

    cout << prev[m-1] << '\n';
}
  

Vizualna DP tabela — Zadatak 5 (Grid sa preprekama)

Označili smo prepreke sa X. Ćelija dp[i][j] predstavlja maksimalnu sumu puta do polja (i,j).

i \ j	0	1	2	3	4
0	0	2	5	9	10
1	2	X	6	X	8
2	5	7	X	7	11
3	X	11	X	9	12
4	13	12	15	10	14

Objašnjenje čitanja:
- Ćelija dp[1][2] = 6 znači maksimalna suma puta do polja (1,2) je 6, izbegavajući prepreke. - Ćelija označena X je prepreka, nema puta kroz nju. - Krajnje polje dp[4][4] = 14 daje maksimalnu sumu puta kroz celokupan grid.

Ova tabela pomaže da učenici vizualizuju kako DP „teče“ kroz grid, koje puteve ignoriše zbog prepreka i gde se sabiraju vrednosti.

Interaktivna DP tabela — Zadatak 5

Hover iznad ćelije da vidiš odakle dolazi maksimalna suma.

Zadatak 7: Domski Sletač — minimalno ukupno pomeranje

Data je matrica dimenzija N × M gde svako polje sadrži broj neistomišljenika.

Domski Sletač kreće iz gornjeg levog ugla i želi da stigne do donjeg desnog ugla, krećući se samo:

• udesno →
• nadole ↓

Kada izabere putanju, svi neistomišljenici se pomeraju do najbližeg polja na toj putanji, takođe krećući se samo:

• udesno →
• nadole ↓

Potrebno je pronaći minimalnu ukupnu udaljenost koju će svi zajedno preći.

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Na prvi pogled deluje da treba:

• generisati sve moguće putanje
• za svaku računati udaljenosti svih ljudi

Međutim, broj putanja je ogroman:

C(N+M-2, N-1)

Zato je potrebno pronaći pametniji pristup.

---

Ključna ideja

Putanju gradimo postepeno pomoću DP-a.

Kada se nalazimo u polju (i,j), postoje samo dva načina da do njega stignemo:

• odozgo → iz (i-1,j)
• sleva → iz (i,j-1)

Dakle:

dp[i][j] =
    min(
        dp[i-1][j] + nova_cena_odozgo,
        dp[i][j-1] + nova_cena_sleva
    )

Problem je što:

• cena nije unapred poznata
• već mora da se izračuna

---

Šta znači "nova cena"?

Kada dođemo u polje (i,j):

• ako smo došli odozgo — dodali smo novu kolonu puta udesno
• ako smo došli sleva — dodali smo novi red puta nadole

Tada određeni neistomišljenici prvi put mogu da „dotaknu“ putanju.

Upravo tada plaćamo njihov doprinos.

---

Dolazak odozgo

Dolazimo iz:

(i-1, j)

Tada putanja prvi put prolazi kroz polje:

(i, j)

Sada svi ljudi u trenutnom redu:

(i,1), (i,2), ... , (i,j-1)

mogu da dođu do puta pomeranjem udesno.

Ako se neko nalazi u koloni:

k

onda mora da pređe:

(j - k)

koraka.

---

Naivno računanje

Mogli bismo svaki put raditi:

for(k = 1; k < j; k++)
    suma += a[i][k] * (j-k);

Ali to bi bilo presporo:

O(N * M * M)

---

Optimizacija prefiksnim sumama

Formula:

Σ a[i][k] * (j-k)

može da se transformiše:

Σ a[i][k] * j - Σ a[i][k] * k

pošto je j konstanta:

= j * Σ a[i][k] - Σ(a[i][k] * k)

Zato pamtimo:

• suma_reda → zbir elemenata ulevo
• suma_reda_tezinska → zbir a[i][k] * k

Tada celu cenu računamo u:

O(1)

---

Dolazak sleva

Analogno:

• posmatramo ljude iznad trenutnog polja
• oni se kreću nadole

Naivno:

for(r = 1; r < i; r++)
    suma += a[r][j] * (i-r);

gde je:

• r = trenutni red koji obilazimo

Koristimo formulu:

Σ a[r][j] * (i-r)
=
i * Σ a[r][j]
-
Σ(a[r][j] * r)

Zato pamtimo:

• suma_kolona[j]
• suma_kolona_tezinska[j]

---

Vizuelna ideja

Primer:

. . . . .
. . X . .
. . . . .
. . . . .

Pretpostavimo da upravo ulazimo u polje X.

Ako dolazimo odozgo:
→ ljudi LEVO od X prvi put mogu do puta

Ako dolazimo sleva:
→ ljudi IZNAD X prvi put mogu do puta

---

Složenost

Svako polje obrađujemo tačno jednom.

Sve dodatne operacije su:

O(1)

Ukupna složenost:

O(N * M)

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

    int broj_redova, broj_kolona;
    cin >> broj_redova >> broj_kolona;

    const ll INF = (1LL << 62);

    // ---------------------------------------------------------
    // dp_prethodni[j]
    // minimalna cena za polje (i-1, j)
    //
    // dp_trenutni[j]
    // minimalna cena za polje (i, j)
    // ---------------------------------------------------------

    vector<ll> dp_prethodni(broj_kolona + 1, INF);
    vector<ll> dp_trenutni(broj_kolona + 1, INF);

    // ---------------------------------------------------------
    // PREFIKSNE SUME PO KOLONAMA
    // ---------------------------------------------------------
    //
    // suma_kolona[j]
    // = zbir svih a[r][j] za r < i
    //
    // suma_kolona_tezinska[j]
    // = zbir svih a[r][j] * r
    //
    // Ovo koristimo za brzo računanje:
    //
    // Σ a[r][j] * (i-r)
    //
    // bez prolaska kroz celu kolonu.
    // ---------------------------------------------------------

    vector<ll> suma_kolona(broj_kolona + 1, 0);
    vector<ll> suma_kolona_tezinska(broj_kolona + 1, 0);

    // ---------------------------------------------------------
    // OBRADA REDOVA
    // ---------------------------------------------------------

    for (int i = 1; i <= broj_redova; i++) {

        fill(dp_trenutni.begin(),
             dp_trenutni.end(),
             INF);

        // -----------------------------------------------------
        // PREFIKSI U TRENUTNOM REDU
        // -----------------------------------------------------
        //
        // suma_reda
        // = zbir svih elemenata ulevo
        //
        // suma_reda_tezinska
        // = zbir a[i][k] * k
        //
        // k predstavlja kolonu koju trenutno sabiramo.
        // -----------------------------------------------------

        ll suma_reda = 0;
        ll suma_reda_tezinska = 0;

        for (int j = 1; j <= broj_kolona; j++) {

            ll broj_ljudi;
            cin >> broj_ljudi;

            // -------------------------------------------------
            // POČETNO POLJE
            // -------------------------------------------------

            if (i == 1 && j == 1) {
                dp_trenutni[j] = 0;
            }
            else {

                ll najbolja_cena = INF;

                // =================================================
                // 1) DOLAZAK ODOZGO
                // =================================================
                //
                // Putanja dolazi iz:
                //
                // (i-1, j)
                //
                // Tada ljudi iz trenutnog reda,
                // LEVO od j,
                // prvi put mogu do puta.
                //
                // Polja:
                //
                // (i,1), (i,2), ... , (i,j-1)
                //
                // Ako je neko u koloni k:
                //
                // prelazi:
                //
                // (j-k)
                //
                // koraka.
                //
                // Naivno:
                //
                // for(k=1; k<j; k++)
                //     suma += a[i][k] * (j-k);
                //
                // Formula:
                //
                // Σ a[i][k] * (j-k)
                //
                // =
                //
                // j * Σ a[i][k]
                // -
                // Σ (a[i][k] * k)
                //
                // =================================================

                if (i > 1) {

                    ll cena_nadole =
                        j * suma_reda
                        - suma_reda_tezinska;

                    najbolja_cena =
                        min(najbolja_cena,
                            dp_prethodni[j]
                            + cena_nadole);
                }

                // =================================================
                // 2) DOLAZAK SLEVA
                // =================================================
                //
                // Putanja dolazi iz:
                //
                // (i, j-1)
                //
                // Tada ljudi iznad trenutnog polja
                // prvi put mogu do puta.
                //
                // Polja:
                //
                // (1,j), (2,j), ... , (i-1,j)
                //
                // Ako je neko u redu r:
                //
                // prelazi:
                //
                // (i-r)
                //
                // koraka.
                //
                // Naivno:
                //
                // for(r=1; r<i; r++)
                //     suma += a[r][j] * (i-r);
                //
                // Formula:
                //
                // Σ a[r][j] * (i-r)
                //
                // =
                //
                // i * Σ a[r][j]
                // -
                // Σ(a[r][j] * r)
                //
                // =================================================

                if (j > 1) {

                    ll cena_udesno =
                        i * suma_kolona[j]
                        - suma_kolona_tezinska[j];

                    najbolja_cena =
                        min(najbolja_cena,
                            dp_trenutni[j - 1]
                            + cena_udesno);
                }

                dp_trenutni[j] = najbolja_cena;
            }

            // =====================================================
            // AŽURIRANJE PREFIKSA
            // =====================================================

            // --- red ---
            suma_reda += broj_ljudi;
            suma_reda_tezinska += broj_ljudi * j;

            // --- kolona ---
            suma_kolona[j] += broj_ljudi;
            suma_kolona_tezinska[j] += broj_ljudi * i;
        }

        // sledeći red postaje prethodni
        dp_prethodni.swap(dp_trenutni);
    }

    cout << dp_prethodni[broj_kolona] << "\n";

    return 0;
}

Završno objašnjenje

Ovaj zadatak je odličan primer kombinovanja:

• dinamičkog programiranja (DP)
• prefiksnih suma
• matematičke transformacije formule

---

Najvažnija ideja

Ne računamo celu cenu ispočetka za svako polje.

Umesto toga:

• putanju širimo korak po korak
• svaki neistomišljenik doprinosi tačno jednom
• taj doprinos dodajemo kada putanja prvi put postane dostupna tom polju

---

Zašto prefiksi?

Naivno bismo morali:

• za svaki red prolaziti kroz sve kolone ulevo
• za svaku kolonu prolaziti kroz sve redove iznad

To bi bilo:

O(N * M * (N+M))

Prefiksne sume omogućavaju:

• da svaki doprinos računamo u O(1)
• bez dodatnih petlji

---

Ključna lekcija

Kod težih DP zadataka:

• nije dovoljno znati standardnu DP formulu
• najvažnije je pravilno modelovati doprinos svakog elementa

U ovom zadatku:

• DP određuje najbolju putanju
• prefiksne sume omogućavaju brzo računanje cena

Skriveni mini kviz — Grid DP (2D DP problem)

Klikni da proveriš svoje znanje o osnovama Grid DP i prepreka!

Otvori kviz

Mini kviz: Da li razumeš Grid DP i prepreke?

1. Koja je standardna DP relacija za maksimalnu sumu puta u gridu (bez prepreka)?

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[i][j] = min(dp[i-1][j], dp[i][j-1])
Prikaži odgovor

2. Kako tretiramo prepreku u gridu?

Postavimo dp[i][j] = -1 ili neki sentinel i ignorišemo pri računanju
Dodamo vrednost prepreke u dp[i][j]
Uzimamo prosečnu vrednost susednih polja
Prikaži odgovor

3. Koji je osnovni princip rekonstrukcije optimalnog puta u grid DP?

Krenuti od dp[n-1][m-1] i pratiti iz koje ćelije dolazi maksimum (gore ili levo)
Samo dodati sve vrednosti reda i kolone
Koristiti brute-force sve moguće puteve
Prikaži odgovor

4. Šta se dešava sa dp[i][j] ako su i=0 ili j=0?

dp[i][j] = 0 ili grid[i][j] (zavisno od inicijalizacije)
dp[i][j] = -1
dp[i][j] se računa kao za ostala polja
Prikaži odgovor

5. Kada je Grid DP problem s preprekama pogodan za takmičenje?

Kada su dimenzije grida male (n,m ≤ 500) i prepreke ograničene
Kada su dimenzije ogromne i prepreke nebitne
Kada koristi memoizaciju za sve polja grida
Prikaži odgovor

Resetuj kviz

4. Povezane stranice

• Uvod u DP — osnovna ideja i tehnike
• DP: Fibonacci sa memoizacijom
• DP: Subset Sum problem
• Algoritmi — DP u širem kontekstu (rekurzija i DP)
• Priprema za takmičenja — 2D DP i napredni primeri

5. Spoljašnji resursi za dalje učenje

• Dynamic Programming — GeeksforGeeks (tekstualni tutorijali)
• DP on Grids — GeeksforGeeks praksa i objašnjenja
• AtCoder Educational DP Contest — takmičarski zadaci za DP
• Grid‑based DP tutoriali (YouTube pretraga)
• CP‑Algorithms — Napredni DP koncepti (Division & Conquer, Memory optimizations)

6. Preporučene knjige i online kursevi

• “Introduction to Algorithms” (Cormen, Leiserson, Rivest, Stein) — klasična knjiga koja detaljno pokriva DP paradigmu i njene primene.
• “Competitive Programming 3” (Steven Halim) — praktični primeri i takmičarski problemi sa DP-jem, grid problemima i optimizacijama.
• MIT OCW 6.006 — Introduction to Algorithms — besplatan online kurs sa predavanjima, problem setovima i DP lekcijama.
• Coursera: Algorithms Part I (Princeton) — detaljna obrada osnovnih i naprednih DP problema kroz praktične zadatke.
• freeCodeCamp — Dynamic Programming for Beginners — interaktivni tutorijal sa vizuelnim primerima i praktičnim zadacima.