Drum de cost minim în matrice: dreapta și jos, C++

Într-o matrice de costuri, pornim din stânga sus și ajungem în dreapta jos folosind numai pași la dreapta sau în jos. Plătim costul fiecărei celule vizitate, inclusiv al celei inițiale și al celei finale. Cerința este despre suma costurilor, nu despre numărul de pași.

Ultimul pas are două origini

La celula (i,j) putem ajunge numai din (i-1,j) sau din (i,j-1). Dacă știm costurile minime până la aceste două celule, alegem varianta mai ieftină și adăugăm costul curent. Aceasta este o tranziție de programare dinamică: reutilizăm răspunsuri deja calculate.

Citim 1≤n,m≤100 și costuri întregi între 0 și 10^6. Nu există obstacole. Afișăm costul minim. Indicii sunt de la zero, iar tablourile clasice rezervă 100×100 celule; numai dreptunghiul n×m reprezintă date valide.

Marginile nu au doi predecesori

În prima celulă, costul minim este chiar a[0][0]. Pe prima linie putem veni numai din stânga, iar pe prima coloană numai de sus. Calculăm aceste două margini separat înainte de interior.

Inițializarea tuturor stărilor cu zero și folosirea minimului fără tratarea marginilor ar permite drumuri fictive care intră gratuit din afara matricei. Valorile inițiale trebuie să descrie drumuri reale, nu doar să evite variabile neinițializate.

În matricea de costuri 1,9,1 / 1,1,1, drumul în jos, dreapta, dreapta costă 4. Celula cu 9 este ocolită.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,m; cin >> n >> m; long long a[100][100],dp[100][100];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    dp[0][0]=a[0][0];
    for(int i=1;i<n;++i) dp[i][0]=dp[i-1][0]+a[i][0];
    for(int j=1;j<m;++j) dp[0][j]=dp[0][j-1]+a[0][j];
    for(int i=1;i<n;++i) for(int j=1;j<m;++j)
        dp[i][j]=a[i][j]+min(dp[i-1][j],dp[i][j-1]);
    cout << dp[n-1][m-1] << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,m; cin >> n >> m; vector<vector<long long>> a(n,vector<long long>(m)),dp(n,vector<long long>(m));
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    dp[0][0]=a[0][0];
    for(int i=1;i<n;++i) dp[i][0]=dp[i-1][0]+a[i][0];
    for(int j=1;j<m;++j) dp[0][j]=dp[0][j-1]+a[0][j];
    for(int i=1;i<n;++i) for(int j=1;j<m;++j)
        dp[i][j]=a[i][j]+min(dp[i-1][j],dp[i][j-1]);
    cout << dp[n-1][m-1] << '\n';
}

Exemplu verificabil fără calculator

Pentru liniile 1 9 1 și 1 1 1, traseul de cost minim coboară imediat, apoi merge la dreapta de două ori. Costul este 1+1+1+1=4. Matricea costurilor minime devine 1 10 11 / 2 3 4.

Nu alegem drumul comparând numai cele două celule imediat următoare. O alegere locală ieftină poate conduce ulterior spre costuri mari. Starea dp compară costuri ale unor drumuri întregi până la fiecare poziție.

Parcurgem liniile de sus în jos și coloanele de la stânga la dreapta, deci ambii predecesori sunt deja calculați. Timpul este O(n·m), memoria O(n·m). Codul afișează doar costul; pentru traseu trebuie memorată sau reconstruită alegerea predecesorului.

Exersează

O singură celulă cu valoarea 7 produce 7, nu zero. Pentru o linie, rezultatul este suma tuturor valorilor ei. Testează o coloană și o matrice cu toate costurile zero. Explică de ce orice drum valid are n+m-1 celule, chiar dacă sumele lor diferă.

Continuă cu drumurile în matrice, drumurile cu obstacole și programarea dinamică.

Întrebări frecvente

Cum calculez drumul de cost minim cu pași la dreapta și în jos?

Pentru fiecare celulă, adaugă costul ei la minimul costurilor accesibile din sus și din stânga. Ordinea pe linii sau coloane trebuie să prelucreze acești predecesori înaintea celulei curente.

Se include costul celulei de pornire?

Da în această lecție, la fel și costul destinației. Inițializarea trebuie să includă prima celulă; altfel toate rezultatele pot fi deplasate cu costul ei.

De ce nu am nevoie de Dijkstra pentru această problemă?

Mișcările numai la dreapta și în jos nu permit revenirea în celule anterioare. Dependențele sunt aciclice și pot fi rezolvate direct prin programare dinamică în O(n·m).