Programare dinamică: drumuri într-o matrice

Programarea dinamică rezolvă subprobleme ale căror rezultate se reutilizează. Definim o stare, o relație de tranziție, condiții inițiale și o ordine de calcul. Exemplul numără drumurile de la colțul stânga-sus la colțul dreapta-jos al unei matrice, cu mișcări numai la dreapta și în jos.

Nu memorăm toate traseele. Păstrăm numărul traseelor care ajung în fiecare celulă. Diferența dintre a număra soluțiile și a le genera permite reducerea unui număr foarte mare de trasee la un tabel cu n*m stări.

Cum funcționează

Definim d[i][j] drept numărul drumurilor până în celula (i,j), cu indici de la unu. Ultimul pas vine fie de sus, fie din stânga. Cele două familii nu se suprapun, deoarece au ultimul pas diferit. Prin urmare, d[i][j]=d[i-1][j]+d[i][j-1].

Celula de start primește unu: există un singur drum vid până la poziția inițială. Linia zero și coloana zero rămân zero și joacă rolul unor margini artificiale. Nu aplicăm formula peste start, fiindcă am suprascrie condiția inițială cu zero. Calculul pe linii funcționează deoarece vecinul de sus și cel din stânga sunt deja cunoscuți.

O recursie simplă ar recalcula aceleași stări de multe ori. Memorarea rezultatelor, numită memoizare, este o variantă de sus în jos. Tabelarea folosită aici construiește iterativ de la stările mici. Ambele cer aceeași definiție corectă a subproblemei; un tabel adăugat unui algoritm greșit nu îl transformă într-o soluție corectă.

Exemplu urmărit pas cu pas

Într-o matrice 3x3, prima linie și prima coloană au câte un drum pentru fiecare celulă. Celula (2,2) primește 1+1=2, celula (2,3) primește 1+2=3, iar (3,3) primește 3+3=6.

Programul presupune 1 <= n,m <= 20, fără obstacole. Numărul maxim din acest domeniu încape în long long. Pentru dimensiuni mai mari poate fi nevoie de calcul modulo o valoare dată sau de numere mari. Această alegere trebuie făcută înainte de a pretinde că formula este suficientă pentru orice matrice.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, m;
    std::cin >> n >> m;
    long long d[21][21] = {};
    d[1][1] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (i != 1 || j != 1)
                d[i][j] = d[i - 1][j] + d[i][j - 1];
    std::cout << d[n][m] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<long long>> d(n + 1, std::vector<long long>(m + 1, 0));
    d[1][1] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (i != 1 || j != 1)
                d[i][j] = d[i - 1][j] + d[i][j - 1];
    std::cout << d[n][m] << '\n';
}

De ce funcționează și cât costă

Orice drum către o celulă diferită de start are exact unul dintre cele două ultime segmente permise. Separarea după ultimul pas este completă și fără dubluri. Inducția în ordinea liniilor și coloanelor justifică fiecare valoare calculată.

Timpul este O(nm), memoria tabelului este O(nm). Deoarece folosim doar linia precedentă și valorile deja calculate pe linia curentă, memoria poate fi redusă la O(m), dacă nu avem nevoie ulterior de întregul tabel.

Greșeli frecvente

Dacă adaugi obstacole, celulele blocate trebuie să aibă valoarea zero, inclusiv startul când este blocat. Dacă permiți deplasări în toate direcțiile, pot apărea cicluri și formula nu mai descrie aceeași problemă.

Exersează

Câte drumuri există într-o matrice cu două linii și patru coloane? Identifică cele patru poziții posibile ale singurului pas în jos.

Rezolvare explicată: Există patru drumuri. Fiecare conține trei pași spre dreapta și unul în jos; poziția acestui pas între cele patru mișcări determină unic traseul.

Continuă să înveți

Matrice, recursivitate și complexitate.

Întrebări frecvente

Ce este o stare în programarea dinamică?

Este o subproblemă descrisă suficient de precis încât rezultatul ei să poată fi reutilizat. Aici, starea este numărul drumurilor până la o anumită celulă.

De ce adunăm și nu luăm maximul?

Cerința numără toate drumurile. Familiile după ultimul pas sunt disjuncte, deci cardinalitățile se adună. Pentru un cost minim sau maxim, tranziția ar fi diferită.

De ce startul are valoarea unu?

Există un singur mod de a fi la start fără să faci niciun pas. Această condiție inițială permite propagarea corectă către vecinii accesibili.

Care este diferența dintre memoizare și tabelare?

Memoizarea calculează la cerere și păstrează rezultatele, de obicei recursiv. Tabelarea stabilește o ordine iterativă în care dependențele sunt deja rezolvate.

Funcționează formula dacă merg și în sus?

Nu direct. Mișcările înapoi schimbă dependențele și pot crea cicluri. Trebuie redefinită problema, inclusiv dacă sunt permise vizite repetate.