Bez naslova

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

⚠️ Pre nego što pogledate rešenje

Pokušajte najpre da sami razmislite kako biste obišli sve moguće puteve u matrici. Ovaj zadatak je odličan za vežbu backtracking pristupa i razumevanje eksponencijalne složenosti.

Ovo rešenje koristi jednostavan backtracking pristup, gde se isprobavaju svi mogući putevi od gornjeg levog do donjeg desnog ugla matrice. U svakom koraku moguće je kretanje nadole ili udesno, a trenutni zbir se akumulira.

Iako je idejno vrlo jednostavno, ovaj pristup ima ekstremno lošu efikasnost jer broj puteva raste eksponencijalno sa veličinom matrice.

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

using namespace std;

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

// globalni maksimum
int maxZbirGlobal = -1e9;

void backtrack(int i, int j, int trenutniZbir) {

    // ako smo van matrice
    if (i >= n || j >= n)
        return;

    // dodaj trenutnu vrednost
    trenutniZbir += matrica[i][j];

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

    // kretanje dole
    backtrack(i + 1, j, trenutniZbir);

    // kretanje desno
    backtrack(i, j + 1, trenutniZbir);
}

int main() {

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

    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

Funkcija backtrack istražuje sve moguće puteve kroz matricu. Na svakom polju se dodaje vrednost u trenutni zbir, a zatim se rekurzivno ide dole ili desno.

Kada se stigne do donjeg desnog ugla, proverava se da li je trenutni zbir veći od globalnog maksimuma maxZbirGlobal.

Zbog toga što se ispituju svi putevi, broj mogućnosti raste približno kao: 2^(2n-2), pa je ovo rešenje pogodno samo za male matrice.

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)

⚠️ Pre nego što pogledate rešenje

Pokušajte prvo da razmislite kako biste izbegli ponovno računanje istih putanja u matrici. Ovaj zadatak uvodi jednu od ključnih ideja dinamičkog programiranja — memoizaciju.

Ovo rešenje koristi rekurziju uz memoizaciju kako bi se izbeglo ponavljanje izračunavanja za ista polja matrice. Funkcija maxZbir(i,j) računa maksimalan zbir od pozicije (i,j) do donjeg desnog ugla.

Ako je rezultat za neko polje već izračunat, on se odmah preuzima iz memorije, što značajno smanjuje broj operacija.

Složenost ovog pristupa je O(n²), jer se svako polje računa najviše jednom.

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:

Početak: učitaj dimenziju n i matricu mat[n][n].
Inicijalizacija DP matrice:
- Postavi dp[0][0] = mat[0][0].
- Popuni prvu vrstu i prvu kolonu DP matrice.
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]).
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

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

⚠️ Pre nego što pogledate rešenje

Pokušajte da sami razmislite kako biste rešili problem bez rekurzije, tako što biste postupno gradili optimalna rešenja od početka matrice. Ovo je klasičan primer dinamičkog programiranja.

U ovom pristupu kreiramo DP matricu dp[i][j] koja čuva maksimalan zbir od početnog polja (0,0) do polja (i,j).

Ideja je da se svako polje izračunava na osnovu prethodno izračunatih vrednosti (gore i levo), čime se izbegava rekurzija i ponavljanje računanja.

Kompleksnost ovog pristupa je O(n²) i predstavlja standardno optimalno rešenje za ovaj problem.

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

using namespace std;

int main() {

    int n;
    cin >> n;

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

    // DP matrica:
    // dp[i][j] = maksimalan zbir od (0,0) do (i,j)
    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 tačka (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++) {

            // Preskačemo početno polje jer je već postavljeno
            if (i == 0 && j == 0)
                continue;

            // Prva vrsta: može se doći samo s leva
            if (i == 0) {
                dp[i][j] = matrica[i][j] + dp[i][j - 1];
            }

            // Prva kolona: može se doći samo odozgo
            else if (j == 0) {
                dp[i][j] = matrica[i][j] + dp[i - 1][j];
            }

            // Ostala polja: biramo bolji put (gore ili levo)
            else {
                dp[i][j] = matrica[i][j] +
                           max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Rezultat se nalazi u donjem desnom uglu
    cout << dp[n - 1][n - 1] << endl;

    return 0;
}

Objašnjenje koda

DP matrica dp[i][j] čuva maksimalan zbir koji se može dobiti dolaskom od početnog polja (0,0) do polja (i,j).

Prvo se popunjava početno polje, zatim prva vrsta i prva kolona, jer do njih možemo doći samo iz jednog pravca.

Za sva ostala polja bira se veći od dva moguća prethodna puta (gore ili levo), i dodaje se vrednost trenutnog polja.

Konačan rezultat nalazi se u dp[n-1][n-1]. Ovo rešenje ima optimalnu složenost O(n²).

Prethodno
|<Priprema za drzavno takmičenje i SIO

Maksimalni zbir na putu kroz matricu — rešenje

Uvod

Rešenje 1 — Backtracking bez optimizacije

Objašnjenje koda

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

Primer matrice

Objašnjenje koda

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

Uvod i opis problema

Ideja rešenja

Opis algoritma (idejna struktura dijagrama)

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

Objašnjenje koda