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

Practic valoarea din vector ne memorează infomația ce ne spune rezultatul, iar dimensiunea acesteia, i, ne spune pentru a câta treapta se întâmplă. Totul se reduce la găsirea informațiilor de care avem nevoie și păstrarea lor într-o structură de date cu una, două sau mai multe dimensiuni, în care valoarea stocată reprezintă de obicei răspunsul, iar dimensiunile niște variabile de care trebuie să ținem cont.

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

...

Nu copiați sursa pur și simplu! Problema mai cere ceva!