Prof.

Mihaela Ildegez

Programare dinamică
Programarea dinamică este în principal o optimizare a recursivităților simple. Oriunde vedem o soluție recursivă
care are apeluri repetate pentru aceleași intrări, o putem optimiza folosind programare dinamică.

Ideea este de a stoca pur și simplu rezultatele subproblemelor, astfel încât să nu fie necesar să le re-calculăm atunci
când va fi nevoie mai târziu. Această simplă optimizare reduce complexitatea timpului de la exponențial la polinomial.

De exemplu, dacă scriem o soluție recursivă simplă pentru numere Fibonacci, obținem o complexitate de timp
exponențială și dacă o optimizăm stocând soluții de subprobleme, complexitatea timpului se reduce la liniar.

Complexitate exponențială Complexitate liniara

int efib(int n) int liniarfib(int n)
{if(n<=1) { int f[10000];
return n; f[0]=0;
return efib(n-1)+efib(n-2); f[1]=1;
} for(int i=2;i<=n; i++)
f[i]=f[i-1]+f[i-2];
return f[n];
}
Cum sa rezolv o problema prin metoda de programare dinamica

Urmează două moduri diferite de a stoca valorile, astfel încât valorile unei sub-probleme să poată fi reutilizate. Aici,
vom discuta două modele de rezolvare a problemei DP:

 Bottom Up (Tabulare: în jos)

 Top Down DP (Amintire: de sus în jos)
Programarea dinamică (DP) este o tehnică care rezolvă anumite tipuri de probleme specifice în timp polinomial.
Soluțiile de programare dinamică sunt mai rapide decât metoda brută exponențială și pot fi dovedite cu ușurință pentru
corectitudinea lor. Înainte de a studia cum să gândim dinamic pentru o problemă, trebuie să învățăm:

 Suprapunerea Subproblemelor
 Găsirea proprietății optimă a subproblemei

Pași pentru soluționarea unei rezolvări cu programare dinamică:

1) Identificați dacă este o problemă DP
2) Decideți o expresie de stare cu parametrii de minim
3) Formulează relația de stare
4) Faceți tabularea (sau adăugați memorizarea)

#385 SumTri

Se consideră un triunghi de numere naturale format din n linii. Prima linie conține un număr, a doua linie
conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume
cu n elemente, astfel:

 termenul i al sumei se află pe linia i din triunghi

 pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană,
sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mare sumă care se poate obține în acest mod.
Date de intrare
Fișierul de intrare sumtri.in conține pe prima linie numărul n. Fiecare dintre următoarele n linii conține câte o
linie a triunghiului.
Date de ieșire
Fișierul de ieșire sumtri.out va conține pe prima linie numărul S, reprezentând cea mai mare sumă care se
poate obține.

Restricții și precizări
 1 ≤ n ≤ 100
 numerele din triunghi sunt mai mici decât 1000
sumtri.in sumtri.out
5 21
4
14
213
9443
45221

Exemplu:

Vom lucra în paralel cu două matrice astfel A-matricea inițială și B matricea în care vom construi sumele parțiale:
A 1 2 3 4 5 B 1 2 3 4 5
Linia 1 4 Linia 1 21
Linia 2 1 4 Linia 2 17 14
Linia 3 2 1 3 Linia 3 16 10 9
Linia 4 9 4 4 3 Linia 4 14 9 6 5
Linia 5 4 5 2 2 1 Linia 5 4 5 2 2 1
+
Substructura optimă a sumei maxime în triunghi este dată de relația:

A[i][j], dacă i = n, oricare ar fi j = ̅̅̅̅̅

1, 𝑛
B[i][j]={
𝐴[𝑖][𝑗] + max(𝐵[𝑖 + 1][𝑗], 𝐵[𝑖 + 1][𝑗 + 1]) , 𝑜𝑟𝑖𝑐𝑎𝑟𝑒 𝑎𝑟 𝑓𝑖 𝑖 = (𝑛 − 1) → 1, 𝑠𝑖 𝑗 = 1 → 𝑗

Pentru etapa 1 se trasează copie în matricea B linia n din matricea A. Vom forma apoi triunghiul rezultat
de la bază la vârf, cu sumele maxime care se pot forma cu fiecare număr folosind relația din structura de optim.
Soluția o vom găsi în B[1][1].

#include <fstream>

using namespace std;

ifstream f("sumtri.in");
ofstream g("sumtri.out");

int main()
{
int A[101][101]={0};///matricea initiala
int B[101][101]={0};///matricea suma
int n;

f>>n;
for(int i=1;i<=n; i++)
for(int j=1;j<=i; j++)
f>>A[i][j];
 ///copii linia i din matricea A in matricea B
for(int i=1;i<=n; i++)
B[n][i]=A[n][i];

///formez sumele maxime in B parcurgand matricea suma de jos in sus

///si fiecare linie de la stanga la dreapta
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i; j++)
if(B[i+1][j]>=B[i+1][j+1])
B[i][j]=A[i][j]+B[i+1][j];
else
B[i][j]=A[i][j]+B[i+1][j+1];

g<<B[1][1];///afisez rezultatul
return 0;
}

#386 SumTri1

Se consideră un triunghi de numere naturale format din n linii. Prima linie conține un număr, a doua linie
conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume
cu n elemente, astfel:
 termenul i al sumei se află pe linia i din triunghi
 pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană,
sau pe coloana imediat următoare spre dreapta.
Să se determine cea mai mică sumă care se poate obține în acest mod și numerele care o alcătuiesc.

Date de intrare: Fișierul de intrare sumtri1.in conține pe prima linie numărul n. Fiecare dintre următoarele n linii
conține câte o linie a triunghiului.

Date de ieșire: Fișierul de ieșire sumtri1.out va conține pe prima linie numărul S, reprezentând cea mai mică
sumă care se poate obține. Pe linia următoare se vor afla n numere din triunghi, care sunt termenii sumei minime,
după regula descrisă mai sus.
Restricții și precizări
 1 ≤ n ≤ 100
 numerele din triunghi sunt mai mici decât 1000
Exemplu:
sumtri1.in sumtri1.out
5 17
4 44342
14
993
9443
45256

Indicații: problema e asemănătoare cu cea precedentă. În loc să calculăm suma maximă vom calcula suma
minimă. Acest procedeu se va realiza aproximativ la fel.

Substructura optimă a sumei minime în triunghi este dată de relația:

A[i][j], dacă i = n, oricare ar fi j = ̅̅̅̅̅

1, 𝑛
B[i][j]={
𝐴[𝑖][𝑗] + min(𝐵[𝑖 + 1][𝑗], 𝐵[𝑖 + 1][𝑗 + 1]) , 𝑜𝑟𝑖𝑐𝑎𝑟𝑒 𝑎𝑟 𝑓𝑖 𝑖 = (𝑛 − 1) → 1, 𝑠𝑖 𝑗 = 1 → 𝑗
A 1 2 3 4 5 B 1 2 3 4 5
Linia 1 4 Linia 1 17
Linia 2 1 4 Linia 2 16 13
Linia 3 9 9 3 Linia 3 15 15 9
Linia 4 9 4 4 3 Linia 4 13 6 6 8
Linia 5 4 5 2 5 6 Linia 5 4 5 2 5 6

T 1 2 3 4 5
Linia 1 2
Linia 2 1 3
Linia 3 2 2 3
Linia 4 1 3 3 4
Linia 5 0 0 0 0 0

#include <fstream>
using namespace std;

ifstream f("sumtri.in");
ofstream g("sumtri.out");

int main()
{
int A[101][101]={0}; ///matricea initiala
int B[101][101]={0}; ///matricea suma
int T[101][101]={0};///matricea traseu
int n, i, j;
f>>n;
for(i=1;i<=n; i++)
for( j=1;j<=i; j++)
f>>A[i][j];
///copii linia i din A in B
for(i=1;i<=n; i++)
B[n][i]=A[n][i];

///formez sumele maxime in B de jos in sus si fiecare linie de la stanga la dreapta

for( i=n-1;i>=1;i--)
for( j=1;j<=i; j++)
if(B[i+1][j]<=B[i+1][j+1])
{B[i][j]=A[i][j]+B[i+1][j];
T[i][j]=j;
}
else
{B[i][j]=A[i][j]+B[i+1][j+1];
T[i][j]=j+1;
}
g<<B[1][1]<<'\n';
///afisarea solutiei
i=1; j=1;
while(i<=n)
{g<<A[i][j]<<' ';
j=T[i][j];
i++;
}
return 0;
}
#392 Cladire
Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane.
Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n, m). Din orice
cameră (i,j) se poate ajunge numai în camerele (i+1, j) sau (i, j+1).
Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n, m). Deoarece numărul de
posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

Date de intrare: Fișierul de intrare cladire.in conține pe prima linie numerele n m.

Date de ieșire: Fișierul de ieșire cladire.out va conține pe prima linie numărul P, reprezentând în câte moduri se
poate ajunge din camera (1,1) în camera (n, m), număr afișat modulo 9901.

Restricții și precizări:

 1 ≤ n , m ≤ 1000

Exemplu:
cladire.in cladire.out
33 6
Explicație:

Indicații:

Vom construi o matrice A cu n linii și m coloane în care fiecare element A[i,j] reprezintă numărul de posibilități
prin care se poate ajunge în camera de coordonate i, j, modulo 9901.
Se constată că:

 în oricare dintre camerele de pe linia 1 sau de pe coloana 1 se poate ajunge în exact un mod (venind din
camera din stânga, respectiv de sus), deci A[1,j]=1 și A[i,1]=1.
 într-o cameră de coordonate i,j care nu se află pe prima linie sau pe prima coloană se poate intra din
camera din stânga, de coordonate i,j-1 sau din camera de deasupra, de coordonate i-1,j, deci A[i,j]=A[i-
1,j]+A[i,j-1].

Substructura optimă a numărului de moduri în care se poate ajunge în camera i,j este:

1, dacă 𝑖 = 𝑛, adică plec in camera din stânga

A[i][j]={ dacă j = m, adică plec in camera de sus
1,
A[𝑖 + 1][𝑗] + A[𝑖][𝑗 + 1], adică se poate iesi si din camera in stânga și in de deasupra

Operațiile necesare pentru determinarea valorilor din matrice se fac modulo 9901. Rezultatul se află în
elementul A[1, 1].
#include <fstream>
using namespace std;

ifstream f("cladire.in");
ofstream g("cladire.out");

int a[1001][1001];
int main()
{
int n, m, i, j;
f>>n>>m;

a[n][m]=1; /// o singura posibilitate de a ajunge la iesire sunt deja acolo

for(i=n; i>=1;i--) /// initializez ultima coloana a matricei

a[i][m]=1; ///am o sigura cale, in jos

for(i=m-1;i>=1;i--) ///la fel pentru ultima linie

a[n][i]=1;

for(i=n-1;i>=1;i--)
for(j=m-1;j>=1;j--)///acum calculez nr de posibilitati din fiecare camera
a[i][j]=(a[i+1][j]+a[i][j+1])%9901;

g<<a[1][1];///aici e nr de posibilitati plecand din prima camera

return 0;
}

#393 Clădire 1
La fel ca problema dinainte, dar exista camere blocate prin care nu pot trece

#include <fstream>
using namespace std;
ifstream f("cladire1.in");
ofstream g("cladire1.out");

int a[1001][1001];

int main()
{
int n, m, i, j, k, t;
f>>n>>m;
f>>k;
for(t=1;t<=k;t++)
{
f>>i>>j;
a[i-1][j-1]=-1;
}
//pana aici a fost citirea

a[n-1][m-1]=1; // o singura posibilitate de a ajunge la iesire sunt deja acolo

for(i=n-2;i>=0;i--) // initializez ultima coloana a matricei
if(a[i][m-1]!=-1) //daca nu e blocata
if(a[i+1][m-1]==1)//si pot merge in jos
a[i][m-1]=1; //am o sigura cale, in jos
else
a[i][m-1]=0; //altfel am 0 posibilitati

for(i=m-2;i>=0;i--) //la fel pt ultima linie

if(a[n-1][i]!=-1) //daca nu e blocata
if(a[n-1][i+1]==1 //daca pot sa merg la dreapta
a[n-1][i]=1;
else
a[n-1][i]=0;
 for(i=n-2;i>=0;i--)
for(j=m-2;j>=0;j--)//acum calculez nr de posibilitati din fiecare camera
if(a[i][j]!=-1)//numai daca nu e inchisa
{if(a[i+1][j]!=-1 and a[i][j+1]!=-1)//daca pot sa merg si in jos si la
//dreapta
a[i][j]=(a[i+1][j]+a[i][j+1])%9901;
else
if(a[i+1][j]!=-1 and a[i][j+1]==-1)//daca pot sa merg numai in jos
a[i][j]=(a[i+1][j])%9901;
else
if (a[i+1][j]==-1 and a[i][j+1]!=-1)//daca pot sa merg numai la
//dreapta
a[i][j]=(a[i][j+1])%9901;
else
if(a[i+1][j]==-1 and a[i][j+1]==-1)//daca nu pot sa merg nici
//in jos nici la dreapta
a[i][j]=0;
}

g<<a[0][0];//aici e nr de posibilitati plecand din prima camera

return 0;
}

Cel mai lung subșir comun CMLSC

Se dau două șiruri de elemente X={x1,x2,x3,…,xm}, cu m elemente și Y={y1,y2,y3,...,yn} cu

n elemente. Se cere să se determine un subșir comun de lungime maximă pentru cele două șiruri X și Y.

Exemplu: Fie următoarele două șiruri

X={A, B, C, B, D, A, B} cu m=7 elemente și
Y={B, D, C, A, B, A} cu n=6 elemente
Atunci se observă că exista mai multe subșiruri comune cum ar fi {B,C,A} de lungime 3, {B, C, B, A} de
lungime 4 sau {B, D, A, B} tot de lungime 4(care este cea mai mare valoare a unui subșir comun). Se
observă că pot exista mai multe soluții de lungime maximă.

Definim prefixul i al șirului X ca fiind șirul format din primele i elemente din șir
Prefixul Xi= x1 x2 x3 ... xi ... xm
Poziții: 1 2 3 m m

Structura de optim a unui CMLSC

Dacă avem două șiruri de elemente X={x1,x2,x3,…,xm}, cu m elemente și Y={y1,y2,y3,...,yn}
cu n elemente atunci Z={z1,z2,z3,…,zk}este un CMLSC cu K elemente. El se construiește astfel:
1. Daca xm=yn atunci am găsit un element comun celor două șiruri (xm=yn=zk) și rezultă că mai
trebuie să căutăm CMLSC al șirurilor Xm-1 și Yn-1, deci avem lungimea CMLSC(Xm-1, Yn-1)+1

2. Dacă xm≠yn atunci determina lungimea CMLSC(Xm,Yn-1) și lungimea CMLSC(Xm-1, Yn)ți

vom alege valoare amaximă dintre ele
Substructura optimă a unui CMLSC(Xm, Yn) poate fi scrisă astfel:

0, 𝑑𝑎𝑐ă 𝑖 = 0 ș𝑖 𝑗 = 0
𝑐[𝑖][𝑗] = { 𝑐[𝑖 − 1][𝑗 − 1] + 1, 𝑑𝑎𝑐ă 𝑥𝑖 = 𝑦𝑗 ș𝑖 𝑖 ≠ 0 ș𝑖 𝑗 ≠ 0
max(𝑐[𝑖][𝑗 − 1], 𝑐[𝑖 − 1][𝑗]) , 𝑑𝑎𝑐ă 𝑥𝑖 ≠ 𝑦𝑗 ș𝑖 𝑖 ≠ 0 ș𝑖 𝑗 ≠ 0
 Vom utiliza un tablou bidimensional C cu m+1 linii( de la 0 la m) si n+1 coloane(de la 0 la n) al cărui
elemente le vom calcula în ordinea crescătoare a liniilor( de sus în jos pe linii și de la stânga la dreapta pe coloane).
Inițial vom completa linia 0 și coloana 0 cu valoarea 0. Lungimea maximă a CMLSC(Xm, Yn) se va găsi în C[m][n].
Dacă dorim să afișăm și CMLSC atunci vom utiliza o funcție recursivă care va reconstitui traseul.

Definim direcția cu numere 1, 2, 3 astfel:

1 2
C[i-1][j-1] C[i-1][j]
3 C[i][j-1] C[i][j]

Algoritmul este următorul:

citim șirul X cu m elemente
citim șirul y cu n elemente
pentru i=1,m execută
pentru j=1,n execută
daca x[i] = y[j] atunci
C[i][j]=1+C[i-1][j-1]
B[i][j]= direcția 1
altfel
daca C[i-1][j]≥C[i][j-1] atunci
C[i][j]= C[i-1][j]
B[i][j]= direcția 2
altfel
C[i][j]= C[i][j-1]
B[i][j]= direcția 3
sfDaca
sfDaca
sfPentru
sfPentru

funcția afișareCMLSC(B, X, i, j)
daca i≠0 și j≠0 atunci
daca B[i][j]=1 atunci
afișareCMLSC(B, X, i-1, j-1)
scrie X[i],’ ’
altfel
daca B[i][j]=2 atunci
afișareCMLSC(B, X, i-1, j)
altfel
afișareCMLSC(B, X, i, j-1)
sfDaca
sfDaca
sfDaca
sffuncție

#2528 LungimeSubsirComunMaximal

Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se determine lungimea celui mai lung
subșir comun al lor.
Date de intrare : Fișierul de intrare lungimesubsircomunmaximal.in conține cele două șiruri de caractere, unul
pe prima linie, unul pe cea de-a doua.

Date de ieșire
Fișierul de ieșire lungimesubsircomunmaximal.out va conține pe prima linie numărul L, reprezentând lungimea
subșirului comun maximal al celor două cuvinte.

Restricții și precizări
 1 ≤ lungimea unui șir ≤ 1000

Exemplu:
lungimesubsircomunmaximal.in lungimesubsircomunmaximal.out
aaabcd 4
agahbdert

Indicații:
Vom aplica algoritmul de mai sus dar fără a memora direcțiile de construire a soluției, deoarece se cere
doar determinarea lungimii CMLSC. Aveți grija de faptul că primul element în șirurile de intrare ocupă poziția 0.

#include <fstream>
#include <cstring>
using namespace std;
ifstream f("lungimesubsircomunmaximal.in");
ofstream g("lungimesubsircomunmaximal.out");

int main()
{
char X[1001],Y[1001];
short int C[1002][1002]={0};

f.getline(X,1001);
f.getline(Y,1001);

int m=strlen(X);
int n=strlen(Y);

for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(X[i-1]==Y[j-1])
C[i][j]=1+C[i-1][j-1];
else
if(C[i-1][j]>=C[i][j-1])
C[i][j]=C[i-1][j];
else
C[i][j]=C[i][j-1];

g<<C[m][n];
return 0;
}
Tema1: Monede Byteland - # Programare dinamică (https://www.spoj.com/problems/COINS/)

În Byteland au un sistem monetar foarte ciudat. Fiecare monedă de aur bytelandiană are un număr întreg scris
pe ea. O monedă n poate fi schimbată într-o bancă în trei monede: n / 2, n / 3 și n / 4. Dar aceste cifre sunt toate
rotunjite (băncile trebuie să aducă profit).

De asemenea, puteți vinde monede Bytelandiene pentru dolari americani. Rata de schimb este 1: 1. Dar nu poți
cumpăra monede Bytelandiene.

Cerința: Ai o monedă de aur. Care este suma maximă de dolari americani pe care o puteți obține pentru asta?

Intrare
Intrarea va conține mai multe cazuri de testare (nu mai mult de 10). Fiecare test conține o singură linie pe care
este scris cu un număr natural n. Acesta este numărul scris pe moneda ta.

Ieșire:
Pentru fiecare caz de test rezultatul va fi afișat pe o singură linie, care conține suma maximă de dolari americani
pe care îi puteți face.

Restricții: 0 <= n <= 1 000 000 000

Exemplu
Intrare Ieșire
12 13
2 2

Explicații:
Puteți schimba 12 în 6, 4 și 3, apoi le puteți schimba în 6 $ + 4 $ + 3 $ = 13 $. Dacă încercați să schimbați
moneda 2 în 3 monede mai mici, veți primi 1, 0 și 0, iar mai târziu puteți obține cel mult 1 dolar din ele. Este mai
bine doar să schimbați cele 2 monede direct în 2 dolari.

Tema o aveți pe site-ul pbinfo începând de duminica