Choose your language!

---

|

Maksimalni zbir na putu kroz matricu — rešenje

Uvod

U ovom zadatku radimo sa kvadratnom tabelom dimenzija n × n čija su polja popunjena ciframa od 0 do 9. Igrač počinje u gornjem levom uglu tabele i može da se kreće samo udesno ili nadole, po jedno polje u jednom koraku. Cilj je doći do donjeg desnog ugla tabele na način da zbir vrednosti polja kroz koja igrač prolazi bude maksimalan.

Naivni pristup problemu podrazumeva isprobavanje svih mogućih puteva od početka do kraja tabele. Svaki put se sastoji od tačno 2n−2 koraka, gde je svaki korak ili desno ili nadole. Ovo vodi do eksponencijalnog broja puteva, približno 2^(2n−2), što je izvodljivo samo za male dimenzije matrice, npr. do 10.

Efikasniji pristupi se oslanjaju na dinamičko programiranje. U top-down pristupu sa memoizacijom, za svako polje (i,j) pamti se maksimalni zbir do cilja. Ako je vrednost za neko polje već izračunata, ne računa se ponovo, čime se smanjuje broj operacija i kompleksnost postaje O(n^2). Bottom-up pristup formira DP matricu gde dp[i][j] predstavlja maksimalan zbir do polja (i,j) od početnog polja (0,0), koristeći rekurentnu formulu dp[i][j] = mat[i][j] + max(dp[i-1][j], dp[i][j-1]). Ovaj metod je vrlo efikasan i praktičan za sve n ≤ 30.

Postoji i optimizacija memorije u DP rekurenciji: za izračunavanje dp[i][j] potrebni su samo prethodni i tekući red, što smanjuje potrošnju memorije sa O(n^2) na O(n). Alternativno, heuristički backtracking sa pruning-om može se koristiti za praktičnu akceleraciju, ali je i dalje inferioran u odnosu na DP i uglavnom služi za ilustraciju koncepta.

Zaključak: za matrice dimenzija do 30×30 najbolji izbor je dinamičko programiranje, bilo bottom-up ili top-down sa memoizacijom. Brute force i backtracking su korisni uglavnom za edukaciju i male dimenzije, dok optimizacija memorije predstavlja finu doradu za veće tabele.

Rešenje 1 — Backtracking bez optimizacije

Prvo rešenje koristi jednostavan backtracking pristup, gde se isprobavaju svi mogući putevi od gornjeg levog do donjeg desnog ugla matrice. U svakom koraku igrač može da se pomeri ili nadole ili udesno, a trenutni zbir se akumulira. Kada se stigne do donjeg desnog polja, upoređuje se sa prethodno pronađenim maksimalnim zbirom i eventualno ažurira globalna maksimalna vrednost.

Efikasnost ovog pristupa je vrlo niska za veće matrice jer broj mogućih puteva eksponencijalno raste sa dimenzijom matrice. Konkretno, za matricu dimenzija n × n, broj puteva je približno 2^(2n-2). Ovaj metod je praktičan samo za male dimenzije (n ≤ 10) i služi uglavnom za edukaciju ili provere pravilnosti rešenja.

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

int n;
vector<vector<int>> matrica;
int maxZbirGlobal = -1e9;

void backtrack(int i, int j, int trenutniZbir) {
    // Ako smo van matrice
    if (i >= n || j >= n) return;

    // Dodaj vrednost trenutnog polja
    trenutniZbir += matrica[i][j];

    // Ako smo stigli do cilja (donji desni ugao)
    if (i == n - 1 && j == n - 1) {
        maxZbirGlobal = max(maxZbirGlobal, trenutniZbir);
        return;
    }

    // Inače, probaj oba pravca:
    backtrack(i + 1, j, trenutniZbir); // dole
    backtrack(i, j + 1, trenutniZbir); // desno
}

int main() {
    cin >> n;
    matrica.assign(n, vector<int>(n));

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

    backtrack(0, 0, 0);

    cout << maxZbirGlobal << endl;
    return 0;
}

Objašnjenje koda

Kod definiše globalnu promenljivu maxZbirGlobal koja čuva trenutno najveći pronađeni zbir. Funkcija backtrack prima trenutnu poziciju (i,j) i akumulirani zbir do te pozicije. Ako je trenutna pozicija van matrice, funkcija se odmah prekida. Kada igrač stigne do donjeg desnog ugla, vrednost trenutnog zbira se upoređuje sa maxZbirGlobal i po potrebi ažurira.

U glavnoj funkciji se prvo učitava dimenzija matrice i vrednosti polja. Zatim se poziva backtracking funkcija sa početnom pozicijom (0,0) i trenutnim zbirom 0. Nakon završetka, globalna maksimalna vrednost se ispisuje.

Ovo rešenje ilustruje osnovnu ideju backtrackinga i kako se mogu istražiti sve kombinacije koraka, ali zbog eksponencijalnog broja puteva nije pogodno za veće matrice.

Rešenje 2 — Rekurzija sa memoizacijom (Top-Down DP)

Ova varijanta rešenja koristi rekurziju u kombinaciji sa memoizacijom kako bi se izbeglo ponavljanje izračunavanja za ista polja matrice. Funkcija maxZbir(i,j) računa maksimalan zbir od trenutne pozicije (i,j) do donjeg desnog ugla. Ako je vrednost za to polje već izračunata, funkcija je odmah vraća, čime se značajno smanjuje broj operacija.

Efikasnost ovog pristupa je znatno veća od običnog backtracking-a. Svako polje se računa najviše jednom, tako da je ukupna vremenska kompleksnost O(n^2), a memorijska složenost takođe O(n^2) zbog memo matrice. Ovo rešenje je praktično za sve dimenzije matrica do 30×30, pa i više.

Na primer, za matricu dimenzija 5×5:

4 3 5 7 5
1 9 4 1 3
2 3 5 1 2
1 3 1 2 0
4 6 7 2 1
  

Funkcija maxZbir(0,0) će rekurzivno istražiti puteve, ali koristi memo da ne računa iste delove puta više puta. Krajnji rezultat za ovaj primer je 38, isti kao i u backtracking rešenju.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* Rekurzivno rešenje (top-down DP) */

int n;
vector<vector<int>> matrica;
vector<vector<int>> memo;

int maxZbir(int i, int j) {
    // Ako smo van granica
    if (i >= n || j >= n) return -1e9;

    // Ako smo na poslednjem polju
    if (i == n-1 && j == n-1) return matrica[i][j];

    // Ako je već izračunato
    if (memo[i][j] != -1) return memo[i][j];

    // Inače, probaj oba smera
    int desno = maxZbir(i, j+1);
    int dole  = maxZbir(i+1, j);

    // Zapamti rezultat i vrati
    return memo[i][j] = matrica[i][j] + max(desno, dole);
}

int main() {
    cin >> n;
    matrica.assign(n, vector<int>(n));
    memo.assign(n, vector<int>(n, -1));

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

    cout << maxZbir(0, 0) << endl;
    return 0;
}

Objašnjenje koda

Funkcija maxZbir(i,j) koristi princip memoizacije: za svako polje (i,j) pamti maksimalan zbir do kraja matrice u memo[i][j]. Ako je vrednost već izračunata, funkcija je odmah vraća. Inače, računa maksimalan zbir koristeći oba moguća pravca — desno ili dole — i rezultat čuva u memo.

U glavnoj funkciji se prvo učitava matrica, zatim se inicijalizuje memo matrica sa -1, što označava da vrednosti još nisu izračunate. Poziva se maxZbir(0,0) i rezultat se ispisuje. Ovaj pristup značajno smanjuje broj rekurzivnih poziva u odnosu na običan backtracking, a rezultat je isti — maksimalan zbir puta kroz matricu.

Rešenje 3 — Dinamičko programiranje (Bottom-Up)

Uvod i opis problema

Treća varijanta rešenja koristi dinamičko programiranje u bottom-up pristupu. Cilj je izračunati maksimalan zbir puta od gornjeg levog do donjeg desnog ugla matrice dimenzija n × n. Svaki korak može biti desno ili nadole, a vrednosti polja se akumuliraju. Za razliku od rekurzije sa memoizacijom, bottom-up pristup gradi DP matricu iterativno, izbegavajući rekurzivne pozive.

Ideja rešenja

Glavna ideja je kreirati pomoćnu DP matricu dp[i][j] koja za svako polje (i,j) čuva maksimalan zbir puta od početnog polja (0,0) do tog polja. Prvo se inicijalizuju vrednosti za početno polje, prvu vrstu i prvu kolonu. Zatim se iterativno popunjavaju ostala polja matrice koristeći formulu dp[i][j] = mat[i][j] + max(dp[i-1][j], dp[i][j-1]). Nakon popunjavanja cele DP matrice, rezultat se nalazi u dp[n-1][n-1].

Opis algoritma (idejna struktura dijagrama)

Algoritam se može prikazati sledećim koracima:

1. Početak: učitaj dimenziju n i matricu mat[n][n].
2. Inicijalizacija DP matrice:
   • Postavi dp[0][0] = mat[0][0].
   • Popuni prvu vrstu i prvu kolonu DP matrice.
3. Glavna petlja: za svako polje (i,j) gde su 1 ≤ i,j ≤ n-1, izračunaj dp[i][j] = mat[i][j] + max(dp[i-1][j], dp[i][j-1]).
4. Rezultat: dp[n-1][n-1] sadrži maksimalan zbir puta.

Dijagram toka algoritma je prikazan na slici 1.

Slika 1: Zadatak "Maksimalan zbir na putu kroz matricu " -algoritam, dinamičko programiranje

#include <iostream>
#include <vector>
#include <algorithm> // zbog max

using namespace std;

/* 
Zadatak: Maksimalni zbir na putu kroz matricu
U tabeli dimenzija n×n polja su popunjena ciframa od 0 do 9.
Igrač koji se nalazi u gornjem levom uglu može da ide desno ili dole.
Rešenje se bazira na dinamičkom programiranju (dp[i][j] = maksimalan zbir do polja (i,j)).
*/

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

    // Matrica vrednosti
    vector<vector<int>> matrica(n, vector<int>(n));

    // DP matrica koja pamti maksimalne zbirove
    vector<vector<int>> dp(n, vector<int>(n));

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

    // Početna pozicija (gornji levi ugao)
    dp[0][0] = matrica[0][0];

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

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

            if (i == 0 && j != 0) {
                dp[0][j] = matrica[0][j] + dp[0][j-1];
            }
            else if (j == 0 && i != 0) {
                dp[i][0] = matrica[i][0] + dp[i-1][0];
            }
            else {
                dp[i][j] = matrica[i][j] + max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    // Ispis rešenja (donji desni ugao)
    cout << dp[n-1][n-1] << endl;

    return 0;
}

Objašnjenje koda

U ovom bottom-up pristupu kreiramo DP matricu dp[i][j] koja za svako polje čuva maksimalan zbir puta od početka do tog polja. Početna pozicija dp[0][0] se postavlja na vrednost prvog polja matrice. Prva vrsta i prva kolona se popunjavaju iterativno jer se do njih može doći samo iz jednog pravca (sleva ili odozgo).

Za ostala polja biramo maksimalan zbir između gornjeg i levog suseda, i dodajemo vrednost trenutnog polja. Nakon što se cela DP matrica popuni, maksimalan zbir puta se nalazi u dp[n-1][n-1] i ispisuje se.

Ovaj pristup je vrlo efikasan: vremenska kompleksnost je O(n^2), a memorijska složenost takođe O(n^2). Idealan je za matrice dimenzija do 30×30 i veće, i tipično se koristi u produkcijskim rešenjima.

---

Prethodno
​|< Priprema za drzavno takmičenje i SIO

---