Š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)

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

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

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: 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.
• Uvek testirajte male primere ručno kako biste proverili logiku.

Napredna varijanta: Putanja sa minimalnim ukupnim pomeranjem ljudi

U ovoj varijanti svako polje matrice sadrži broj ljudi. Cilj je da se pronađe putanja od gornjeg levog polja (1,1) do donjeg desnog polja (N,M), uz kretanje samo udesno ili nadole. U ovom naprednom zadatku redovi i kolone numerišu se od 1.

• 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 ljudi 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 ljudi 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:

• „svaka osoba 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 ljudi 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:

• ljudi 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 osoba 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.

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 ljudi 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

Ovde dodajemo novu kolonu:

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

Za primer iznad:

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

Ljudi 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 naprednom zadatku sa minimalnim ukupnim pomeranjem:

• 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

Veza sa naprednim Grid DP

U Zadatku 7 ispod, ponderisane prefiksne sume omogućavaju da se brzo izračunaju dodatne cene pomeranja ljudi. Ovo pokazuje kako se ideje iz rada sa prefiksnim sumama mogu kombinovati sa Grid DP-om da bi se rešili složeniji problemi.

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.

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

1 1 1
1 2 3
1 3 6
    

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.

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

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

Zadatak 3: Grid sa preprekama 5×5

Data je matrica dimenzija 5 × 5, gde 0 označava slobodno polje, a 1 prepreku. Kretanje je dozvoljeno samo desno i dole. Odredi broj puteva od gornjeg levog do donjeg desnog ugla, bez prolaska kroz prepreke.

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

1 1 1 1 1
1 0 1 0 1
1 1 2 2 3
0 1 0 2 5
0 1 1 3 8

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

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

dp[0][0] = grid[0][0], ako početno polje nije prepreka

dp[i][j] = -∞, ako je grid[i][j] == -1

best = max(dp[i-1][j], dp[i][j-1])
       (polja van matrice tretiraju se kao -∞)

dp[i][j] = grid[i][j] + best, ako best != -∞
dp[i][j] = -∞, ako best == -∞

 0   2   5   9  10
 2   X   6  14  16
 5   7   X  15  19
 6  11  13  17  20
 8  12  16  18  22

0 → 2 → 3 → 4 → 5 → 2 → 3 → 1 → 2

0 + 2 + 3 + 4 + 5 + 2 + 3 + 1 + 2 = 22

Za svako polje čuvaj:
- best[i][j]: maksimalnu sumu puta do tog polja
- ways[i][j]: broj puteva koji ostvaruju tu maksimalnu sumu

Uporedi maksimalne sume koje dolaze odozgo i sleva.
Ako su jednake, saberi brojeve odgovarajućih puteva modulo MOD.
Za O(m) memorije čuvaj samo jedan red maksimalnih suma i brojeva puteva.
Modulo primenjuj samo na broj puteva, a ne na maksimalnu sumu.

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

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

    if (n <= 0 || m <= 0) {
        cout << "Neispravne dimenzije\n";
        return 0;
    }

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

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

    const long long NEG_INF =
        numeric_limits<long long>::lowest() / 4;

    vector<vector<long long>> dp(
        n, vector<long long>(m, NEG_INF)
    );

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

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

            if (i == 0 && j == 0)
                continue;

            long long best = NEG_INF;

            if (i > 0)
                best = max(best, dp[i - 1][j]);

            if (j > 0)
                best = max(best, dp[i][j - 1]);

            if (best != NEG_INF)
                dp[i][j] = best + grid[i][j];
        }
    }

    if (dp[n - 1][m - 1] == NEG_INF)
        cout << "Ne postoji validan put\n";
    else
        cout << dp[n - 1][m - 1] << '\n';

    return 0;
}

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

const long long MOD = 1000000007LL;

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

    int n, m;
    cin >> n >> m;

    if (n <= 0 || m <= 0) {
        cout << 0 << '\n';
        return 0;
    }

    vector<long long> best(m, 0);
    vector<long long> ways(m, 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long vrednost;
            cin >> vrednost;

            if (i == 0 && j == 0) {
                best[j] = vrednost;
                ways[j] = 1;
                continue;
            }

            // best[j] sadrži vrednost iz polja iznad.
            long long topBest = (i > 0) ? best[j] : -1;
            long long topWays = (i > 0) ? ways[j] : 0;

            // best[j-1] sadrži vrednost iz polja sleva.
            long long leftBest = (j > 0) ? best[j - 1] : -1;
            long long leftWays = (j > 0) ? ways[j - 1] : 0;

            if (topBest > leftBest) {
                best[j] = topBest + vrednost;
                ways[j] = topWays;
            } else if (leftBest > topBest) {
                best[j] = leftBest + vrednost;
                ways[j] = leftWays;
            } else {
                best[j] = topBest + vrednost;
                ways[j] = (topWays + leftWays) % MOD;
            }
        }
    }

    cout << ways[m - 1] << '\n';
    return 0;
}

Napredni zadatak 7: Minimalno ukupno pomeranje ljudi

Napredni izazov: Ovaj zadatak kombinuje dinamičko programiranje sa ponderisanim prefiksnim sumama. Za razliku od standardnih Grid DP problema, ne brojimo puteve niti minimizujemo zbir vrednosti duž puta, već računamo ukupnu udaljenost koju pređu svi ljudi.

Data je matrica dimenzija N × M. Svako polje a[i][j] sadrži broj ljudi koji se nalaze u tom polju.

Potrebno je izabrati put od gornjeg levog polja (1,1) do donjeg desnog polja (N,M). Putanja može da se kreće samo:

• udesno →
• nadole ↓

Kada se putanja odabere, svaka osoba treba da stigne do najbližeg polja na toj putanji, krećući se takođe samo udesno ili nadole. Udaljenost osobe jednaka je broju koraka potrebnih da stigne do putanje.

Cilj: Pronaći putanju koja minimizuje zbir udaljenosti svih ljudi.

Napomena o indeksiranju: Formule i implementacija ovog zadatka koriste indeksiranje od 1: redovi su numerisani od 1 do N, a kolone od 1 do M. To se razlikuje od prethodnih primera, koji koriste indeksiranje od 0.

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

dp[1][1] = 0

cenaOdozgo = Σ a[i][k] * (j-k), za 1 ≤ k < j

cenaOdozgo = j * sumaReda - ponderisanaSumaReda

cenaSleva = Σ a[r][j] * (i-r), za 1 ≤ r < i

cenaSleva = i * sumaKolone[j] - ponderisanaSumaKolone[j]

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

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

using ll = long long;

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

    int n, m;
    if (!(cin >> n >> m) || n <= 0 || m <= 0) {
        return 0;
    }

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

    // dpPrethodni[j] = minimalna cena do polja (i-1, j)
    // dpTrenutni[j]  = minimalna cena do polja (i, j)
    vector<ll> dpPrethodni(m + 1, INF);
    vector<ll> dpTrenutni(m + 1, INF);

    // Sume polja iznad trenutnog reda, za svaku kolonu.
    vector<ll> sumaKolone(m + 1, 0);
    vector<ll> ponderisanaSumaKolone(m + 1, 0);

    for (int i = 1; i <= n; ++i) {
        fill(dpTrenutni.begin(), dpTrenutni.end(), INF);

        // Sume polja levo od trenutnog polja u ovom redu.
        ll sumaReda = 0;
        ll ponderisanaSumaReda = 0;

        for (int j = 1; j <= m; ++j) {
            ll brojLjudi;
            if (!(cin >> brojLjudi)) {
                return 0;
            }

            if (i == 1 && j == 1) {
                // Početno polje: niko ne mora da se pomera.
                dpTrenutni[j] = 0;
            } else {
                ll najboljaCena = INF;

                // Opcija 1: dolazak odozgo.
                // Ljudi levo od putanje u trenutnom redu kreću se udesno.
                if (i > 1) {
                    ll cenaOdozgo = j * sumaReda - ponderisanaSumaReda;
                    najboljaCena = min(najboljaCena,
                        dpPrethodni[j] + cenaOdozgo);
                }

                // Opcija 2: dolazak sleva.
                // Ljudi iznad putanje u ovoj koloni kreću se nadole.
                if (j > 1) {
                    ll cenaSleva = i * sumaKolone[j]
                        - ponderisanaSumaKolone[j];
                    najboljaCena = min(najboljaCena,
                        dpTrenutni[j - 1] + cenaSleva);
                }

                dpTrenutni[j] = najboljaCena;
            }

            // Dodajemo trenutno polje u prefikse reda.
            sumaReda += brojLjudi;
            ponderisanaSumaReda += brojLjudi * j;

            // Dodajemo trenutno polje u prefikse kolone.
            sumaKolone[j] += brojLjudi;
            ponderisanaSumaKolone[j] += brojLjudi * i;
        }

        // Izračunati red postaje prethodni red.
        dpPrethodni.swap(dpTrenutni);
    }

    cout << dpPrethodni[m] << '\n';
    return 0;
}

2 2
0 5
7 0

5

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

Proveri svoje razumevanje Grid DP-a, brojanja puteva, prepreka i optimalnih putanja.

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.