Grid DP (dinamičko programiranje na mreži)

Grid DP obuhvata klasu problema dinamičkog programiranja u kojima se radi nad matricom (mrežom). Najčešće se traži:

broj puteva od jednog polja do drugog
minimalna ili maksimalna cena puta
da li je moguće stići do cilja uz određena ograničenja

Ovi problemi su veoma česti u algoritamskim zadacima i intervjuima.

Osnovni problem: broj puteva u mreži

Dat je pravougaoni grid dimenzija n × m. Krećemo se iz gornjeg levog ugla (0,0) i želimo da stignemo do donjeg desnog ugla (n-1, m-1).

Dozvoljena su samo kretanja:

udesno
nadole

Zadatak: izračunati ukupan broj različitih puteva.

Zašto dinamičko programiranje?

Do svakog polja možemo stići iz:

polja iznad
polja levo

Broj puteva do nekog polja zavisi od broja puteva do manjih podproblema, što znači da problem ima:

optimalnu podstrukturu
preklapajuće podprobleme

DP stanje

Definišemo:


dp[i][j] = broj puteva do polja (i, j)

Početno stanje:

dp[0][0] = 1 (postoji jedan način da stojimo na početku)

Prelaz:


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

ako su indeksi u granicama matrice.

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;
}

Vremenska i prostorna složenost

Vremenska složenost: O(n · m)
Prostorna složenost: O(n · m)

Česte varijacije Grid DP problema

minimalna cena puta kroz mrežu
maksimalan zbir vrednosti
kretanje i dijagonalno
ograničen broj poteza

Veza sa drugim DP problemima

Grid DP problemi su osnova za razumevanje:

dinamičkog programiranja na matricama
problema sa putevima i preprekama
naprednih DP problema u grafovima

Nakon savladavanja Grid DP-a, lakše se razumeju problemi poput Edit Distance i Longest Common Subsequence.