Probleme diverse de programare dinamică
Voi prezenta rezolvările a câteva probleme de programare dinamică de dificultate aproape medie la nivel de clasa a XI-a, sperând ca acestea să le fie utile și celor din clasele mai mici.
Încălzire: Datorii (Municipală Iași 2009, XI-XII)
Cerință:
Se dă un vector a cu n (n<=1000) numere naturale. Aflați suma maximă a numerelor dintr-un subșir al lui a în care elementele nu sunt pe poziții consecutive (adică nu avem voie să avem a[i] și a[i+1] în subșir) și care obligatoriu îl conține pe a[1].
Rezolvare:
Vom folosi o dinamică cât se poate de standard: dp[i] = suma maximă a unui subșir care are ultimul element a[i] și care respectă proprietățile din enunț. O recurență corectă ar fi:
dp[i] = a[i] + max{dp[j]}, cu j de la 1 la i-2, pentru orice i de la 3 la n.
Cazuri particulare:
dp[1] = a[1];
dp[2] = 0.
Astfel, complexitatea timp a soluției este O(n^2), suficient de bun în acest caz. Răspunsul final este max{dp[i]}, cu i de la 1 la n.
Optimizarea în O(n) este intuitivă: observăm că nu are rost să lăsăm „spații“ mari între elementele alese din a pentru subșir; de fapt, ar trebui să lăsam spații cât mai mici, fără să uităm de obținerea optimalității. Cele mai mici spații pe care le putem lăsa sunt 2 și 3 (din enunț rezultă că nu putem 1, iar orice număr mai mare poate fi descompus în spații de dimensiuni 2 și 3). Așadar, recurența devine:
dp[i] = max(dp[i-2], dp[i-3]) + a[i], pentru orice i de la 3 la n.
Ușor: Trepte2, pbinfo.ro
Cerință:
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, …, i + (k – 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte (inițial se află pe treapta 1). Afișați rezultatul modulo 9001.
Restricții:
n <= 100000, k < n
n*k <= 2000000
Rezolvare:
Vom utiliza următoarea dinamică: dp[i] = numărul de moduri în care putem urca pe treapta i. Pe treapta i putem ajunge de pe treptele i-1, i-2, …., i-k, deci dp[i] va depinde de dp[i-1], dp[i-2], …, dp[i-k]. Mai exact:
dp[i] = ∑dp[i-j], cu j de la 1 la min(k, i), pentru orice i de la 1 la n.
Caz particular:
dp[0] = 1.
Am scris limita superioară a lui j ca min(k, i) pentru ca în cazul i < k să nu iasă j din limitele vectorului dp. Răspunsul va fi stocat în dp[n], rezolvarea fiind de complexitate-timp O(n*k). Nu uitați de restul la 9001!
Ușurel: Trepte2.2, pbinfo.ro
Singura diferență dintre Trepte2 și problema aceasta reprezintă restricțiile, în sensul că nu mai avem o limită superioară a produsului n*k. În alte cuvinte, pentru că n*k în problema anterioară era mic, o rezolvare în O(n*k) era suficient de bună, dar aici produsul poate atinge valori mult mai mari (>10^9), ceea ce înseamnă că dinamica necesită optimizări semnificative pentru a lua punctaj maxim.
Să revenim la recurența din problema anterioară:
dp[i] = ∑dp[i-j], cu j de la 1 la min(k, i).
Observăm că dp[i] este de fapt suma elementelor din subsecvența dp[i-k…i-1]. Putem foarte ușor, în același timp cu tabloul dp, să calculăm și vectorul s, cu semnificația: s[i] = suma primelor i numere din dp. Recurența va deveni:
dacă i > k: dp[i] = s[i-1] – s[i-k-1]
altfel: dp[i] = s[i-1]
și: s[i] = s[i-1] + dp[i].
Astfel, am optimizat recurența de la O(n*k) la O(n), ceea ce este suficient de rapid pentru această problemă. De menționat faptul că în relația lui s[i] putem înlocui pe dp[i] cu prima relație, obținând:
dacă i > k: s[i] = 2*s[i-1] – s[i-k-1]
altfel: s[i] = 2*s[i-1]
Mediu: cntcifsum, pbinfo.ro
Cerință:
Determinați numărul de numere de n cifre și cu suma cifrelor s modulo 666013.
Restricții:
n<=1000;
1<= s <= 9*n.
Rezolvare:
O dinamică într-o singură dimensiune, adică un tablou unidimensional, nu ajunge să ne descrie soluția în mod precis. Dacă am folosi dp[i], cu semnificația numărului de numere cu i cifre, nu avem niciun mod de a controla recurența (ca în problema Trepte2) ca să ne asigurăm că toate numerele pe care le va lua în calcul dp[i] au într-adevăr suma cifrelor s. Dacă dp[i] ar indica numerele cu suma cifrelor i, cel mai probabil vor fi luate în considerare și numere cu mai puțin sau mai mult de n cifre. Așadar, având în vedere și restricțiile relativ mici ale problemei, vom utiliza un tablou bidimensional: dp[i][j] va arăta numărul de numere cu i cifre și suma cifrelor j.
Recurența este ușor de aflat, dacă ne gândim că adaugăm, la sfârșitul unui număr cu i cifre și suma cifrelor j, cifra c: vom obține un număr cu i+1 cifre și suma j+c. Vom obține astfel:
dp[i][j] = ∑dp[i-1][j-c], cu c de la 0 la min(j, 9), pentru orice i de la 2 la n.
Caz particular:
dp[1][j] = 1, pentru j de la 1 la 9.
Cazul particular de mai sus este important, deoarece noi de la i = 2 putem adăuga cifra 0, ceea ce nu se poate pentru i = 1. Răspunsul va fi stocat în dp[n][s].
Dificil: sequences (Shumen 2017), pbinfo.ro
Cerința:
Să se calculeze numărul de șiruri crescătoare de lungime N, cu numere de la 1 la M, în care fiecare element apare de cel mult K ori.
Restricții:
1 <= N <= 30
1 <= M <= 30
1 <= K <= 30
Rezolvare:
Avem mai mulți parametri de luat în seamă la această problemă, iar, ca la cntcifsum, asta înseamnă că va trebui să folosim un tablou multidimensional. Tot asemănător cu cntcifsum, trebuie să ne gândim la formarea acestor șiruri prin adăugarea unui element la sfârșit: dintr-un șir valid de lungime i-1, punând la sfârșit numerele care respectă condițiile din enunț, obținem un șir valid de lungime i. Să ne uităm la condițiile pe care trebuie să le respecte valoarea pusă la sfârșit: trebuie să fie mai mare sau egală cu ultima valoare din șirul din lungime i-1 și, în caz de egalitate, nu trebuie să fie mai mult de K elemente cu aceeași valoare. Astfel, vom folosi tabloul tridimensional dp, cu dp[i][j][k] = numărul de șiruri de lungime i, cu ultima valore j, această ultimă valoare repetându-se de k ori.
Recurența este:
pentru k == 1:
dp[i][j][k] = ∑∑dp[i-1][p][q], cu p de la 1 la j-1 și q de la 1 la k
(adăugăm o valoare nouă în șir și analizăm toate valorile de la sfârșitul șirurilor de lungime i-1)
pentru k > 1: dp[i][j][k] = dp[i-1][j][k-1] (punem o valoare egală)
Cazuri particulare:
dp[1][j][1] = 1, cu j de la 1 la M.
Răspunsul va fi ∑∑dp[N][j][k], cu j de la 1 la M și k de la 1 la K.
Totuși, dinamica poate fi eficientizată mult: putem scăpa de a treia dimensiune, dacă ne gândim că fixăm un k oarecare (k <= K) și adăugăm odată k elemente egale la sfârșitul șirului. Vom avea astfel: dp[i][j] = numărul de șiruri cu i numere și ultima valoare j. Relația de recurență va fi:
dp[i][j] = ∑∑dp[i-k][x], cu k de la 1 la min(K, i) și x de la 0 la j-1.
Caz particular:
dp[0][0] = 1.
Putem scăpa de suma asociată variabilei x modificând puțin definiția lui dp[i][j], care devine: numărul de șiruri cu i numere și ultima valoare cel mult egală cu j. Recurența devine astfel:
dp[i][j] = ∑dp[i-k][j-1], cu k de la 1 la min(K, i),
iar răspunsul va fi stocat în dp[N][M].
O ultimă optimizare este să calculăm, ca în problema Trepte2.2, un tablou de sume parțiale: vom avea astfel s[i][j] = ∑dp[i][it], cu it de la 1 la j. Obținem astfel o complexitate-timp de O(N*M). Oricum, având în vedere limitele minuscule, orice implementare corectă ia punctaj maxim.
modinfo-blog 