Programare Dinamică
Programarea dinamică este vast utilizată în competițiile de algoritmică. Aceasta însă poate să apară într-o formă simplă și la subiectele de admitere. Voi prezenta programarea dinamică așa cum am înțeles-o eu și așa cum consider că este util să fie înțeleasă pentru evitarea confuziilor.
Programarea dinamică se bazează pe reutilizarea unui rezultat deja calculat pentru a ajunge la următorul. Un exemplu foarte bun poate fi problema treptelor care ne spune ca: Se dă o scară cu n trepte. Pornind de la bază, în câte moduri putem urca aceste trepte știind că putem sări fie pe treapta imediat următoare în sus, fie 2 trepte, în sus.
Pe prima treaptă vom putea ajunge mereu într-un sigur mod. Pe a 2-a treaptă
putem ajunge fie de pe prima, fie de la bază. Pe a 3-a putem ajunge fie de pe
prima fie de pe a 2-a. Ce ne spune această observație? Că pe treapta 3 putem
ajunge însumând numărul de posibilități de a ajunge pe treapta 2 și numărul de
posibilități de a ajunge pe treapta 1. Aceasta este o formulă general valabilă:
modalitati(n) = modalitati(n - 1) + modalitati(n - 2)
De cele mai multe ori, când încercăm să scoatem formula unei dinamici, trebuie să ne gândim ce ce informații avem nevoie. În acest caz avem nevoie de numărul treptei și de numărul de modalități. Pentru asta putem construi un vector:
const int NMAX = 1005;
int dp[NMAX]; // dp[i] = dp[i - 1] + dp[i - 2], unde dp[i] este numarul de
// modalitati, iar i este numarul treptei
Ca principiu, atunci când gandim o dinamică, vrem să găsim o formulă generală,
care să meargă pentru orice iterație, care pornește de la prima poziție.
1. Încercăm să găsim o formulă pentru dp[i] sau dp[i][j], etc. Depinde de
ce avem nevoie.
2. Spunem cine este dp[i] sau dp[i][j], etc.
3. Spunem cine sunt i, j, etc.
Pentru problema treptelor avem:
...
dp[0] = 0;
dp[1] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << '\n';
...
Problemă
Acum încercați să găsiți singuri dp-ul pentru termenul n al șirului lui Fibonacci. Soluția se află mai jos.
Solutie
1. Știm că un termen din Fibonacci se obține mereu din suma ultimilor 2.
2. Deci putem determina un dp[i] = dp[i - 1] + dp[i - 2], unde valorile de
început sunt dp[0] = 1 și dp[1] = 1.
...
dp[0] = 1;
dp[1] = 1;
for (int i = 0; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << '\n';
...
Problemă
O altă problemă este Cladire de pe pbInfo. Încercați mai întâi voi să scoateți dinamica. Acest tip de probleme se învață cel mai bine prin a gandi bine problema.
Solutie
1. Observăm din cerință ca dinamica noastră este deja scrisă într-o formă:
se poate ajunge numai în camerele (i+1,j) sau (i,j+1).
2. Deci dinamica noastră ar arăta cam așa: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i][j].
În cerință ni se spunea care va fi căsuța viitoare, iar noi am schimbat-o și am
spus pentru căsuța curentă, care au fost căsuțele tyrecute din care am fi putut
veni.
3. Se spune că pornim din căsuța (1, 1), deci dp[1][1] = 1, iar resul
valorilor sunt inițial 0.
...
dp[1][1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i][j]);
}
}
...