Introducere în programarea dinamică

Introducere

Programarea dinamică (abrev. DP) este un mod de gândire care poate fi folosit pentru rezolvarea problemelor la care trebuie să aflăm fie numărul de soluții corecte pentru un anumit set de date, fie soluția optimă (minim, maxim, etc.).

Pentru a realiza acest lucru, vom descompune problema în mai multe subprobleme, care, luate împreună, să ne obțină răspunsul dorit.

De ce trebuie să știm programare dinamică?

Deși tipurile de probleme menționate anterior se pot rezolva și cu alte tehnici, cum ar fi backtracking, greedy, formulă matematică etc., programarea dinamică vine drept o nouă perspectivă asupra problemelor care ne permite să găsim soluții pentru o mulțime de probleme, păstrând avantajele care ne sunt oferite atât de greedy cât și de backtracking, iar în multe cazuri, devenind abordarea cea mai potrivită, ceea ce face programarea dinamică să devină una dintre cele mai populare tehnici date la concursurile de algoritmică.

Termenii specifici ai programării dinamice

Pentru a explica părțile componente ale oricărei soluții care se bazează pe metoda programării dinamice, vom explica un exemplu foarte simplu, folosindu-ne de șirul lui Fibonacci.

Vom defini șirul lui Fibonacci ca fiind $F\_0 = 1$, $F\_1 = 1$ și $F\_i = F\_{i-1} + F\_{i-2}$.

După cum se poate observa, avem $F\_i$ care reprezintă cel de-al $i$-lea număr Fibonacci, acesta fiind starea pe care o vom calcula, stări pe care le vom găsi în toate problemele ce necesită programare dinamică. Stările vor avea una sau mai multe dimensiuni.

$F\_i = F\_{i-1} + F\_{i-2}$ reprezintă relația de recurență dintre $F\_i$ și valorile precedente. Pasul de la $F\_{i-1}$ sau $F\_{i-2}$ la $F\_{i}$ reprezintă tranzițiile de la o stare la alta.

În cele din urmă, $F\_0 = 1$, $F\_1 = 1$ reprezintă cazurile de bază, cazuri care nu pot fi definite folosind relația de recurență menționată mai sus.

În concluzie, pentru a putea avea o soluție care folosește programarea dinamică, trebuie să ne asigurăm că avem următoarele părți:

• Cazuri de bază
• Stare pe care o calculăm
• Relație de recurență
• Tranzitii

Aceste aspecte pot fi și optimizate în funcție de problemă, aceste optimizări fiind realizabile fie calculând tranzițiile mai rapid, fie reducând numărul de stări, așa cum se va vedea de-a lungul capitolelor ulterioare care abordează tehnica programării dinamice.

Clasificare

În elaborarea unui algoritm care folosește metoda programării dinamice, putem utiliza mai multe abordări.

Tipuri de scriere

• Recursiv

• Iterativ

Modalități de abordare

1. Top-Down DP:

   • Această formă de DP pleacă de la starea finală a problemei, ea utilizând stările anterioare, până la starea inițială pe care o cunoaștem, pentru a-și construi parametrii ei.
   • De obicei această formă de DP este scrisă utilizând recursivitatea

2. Bottom-Up DP:

   • Această formă de DP pleacă de la starea inițială a problemei, ea construind parametrii stărilor următoare care la rândul lor vor face asta până ce ajungem la construirea parametrilor stării finale.
   • De obicei această formă de DP este scrisă utilizând Complete Search-ul

Modalități de tranziție

• Pull-DP: Informația din starea curentă se formează bazându-se pe una sau mai multe stări anterioare.
• Push-DP: Informația din starea curentă se utilizează pentru calcularea unei stării viitoare.

Probleme clasice

Pentru a ne dezvolta intuiția în ceea ce privește această

tehnică, este necesar să înțelegem mecanismul pe care se bazează problemele clasice.

Este esențial să rezolvăm cât mai multe probleme de DP pentru a deveni fluenți în elaborarea soluțiilor.

Problema Frog 1

View Problem

AtCoder

Deschide

Această problemă ne cere să aflăm costul minim de care are nevoie o broască pentru a ajunge de pe prima piatră pe ultima, dacă se poate deplasa doar pe piatra din față sau pe piatra cu două poziții mai în față.

Deoarece restricțiile sunt foarte mari, aplicarea unei soluții care verifică toate variantele posibile folosind Backtracking este imposibilă, iar diverse abordări de tip Greedy, precum saltul spre cea mai apropiată piatră sau spre piatra cu o diferență de înălțime minimă sunt greșite.

Astfel, se impune folosirea unei soluții care folosește metoda programării dinamice, unde putem stoca $dp\[i]$ care va reprezenta suma minimă a diferențelor salturilor necesare pentru a ajunge la poziția $i$, motivul pentru care vrem să facem asta este acela că este important să avem un răspuns optim stocat pentru fiecare poziție în parte.

Pentru a calcula $dp\[i]$, ne vom folosi de informațiile din enunț, și anume faptul că avem voie să sărim pe o poziție aflată la cel mult două unități de poziția curentă, astfel $dp\[i]$ va fi egal cu următoarea formulă:

unde $|x| = \operatorname{abs}(x)$ este valoarea absolută. Cazul de bază constă în faptul că $dp\_1 = 0$ și $dp\_2 = |v\_1 - v\_2|$, iar complexitatea acestei soluții este $\mathcal{O}(n)$.

Mai jos puteți găsi abordarea recursivă și cea iterativă a problemei.

=== "Recursiv"

--8 < --"usor/dp/frog1_rec.cpp"

=== "Iterativ"

--8 < --"usor/dp/frog1_iter.cpp"

Problema Frog 2

View Problem

AtCoder

Deschide

La fel ca la problema precedentă, trebuie să aflăm costul minim de care are nevoie o broască pentru a ajunge de pe prima piatră pe ultima, dacă se poate deplasa cu cel mult $k$ pași la un moment dat.

Spre deosebire de problema precedentă, pentru a calcula $dp\[i]$, ne vom folosi de informațiile din enunț, recurența de la Frog 1 va fi extinsă pentru a acoperi $k$ poziții.

Cazul de bază constă în faptul că $dp\_1 = 0$ și $dp\_2 = |v\_1 - v\_2|$, iar complexitatea acestei soluții este $\mathcal{O}(n \cdot k)$.

=== "Recursiv"

--8 < --"usor/dp/frog2_rec.cpp"

=== "Iterativ"

--8 < --"usor/dp/frog2_iter.cpp"

Problema Moneda

View Problem

PBInfo

Deschide

La început, când ați citit această problemă, probabil v-ați gândit la o rezolvare Greedy (care mai încolo o să vedeți că este Greedy Euristic), prin care ați fi sortat descrescător șirul de monede și ați fi încercat să utilizați denominația cea mai mare, care este mai mică ca S, cât timp puteați. După ați fi continuat cu următoarea denominație cea mai mare care respectă condiția aceasta pentru suma rămasă ș.a.m.d. Ca să vă dovedesc că nu funcționează această modalitate, încercați să rezolvați această problemă, utilizând modalitatea anterior prezentată, având aceste date de intrare ($N$ numărul de monede, apoi $S$ suma și apoi cele $N$ monede):

3
31
7 2 15

Acum că ați încercat să rezolvați problema într-un mod cunoscut vouă, și ați văzut că nu îți garantează un răspuns, haideți să vă prezint o soluție corectă!

Pentru această problem, o să vă prezint soluțiile utilizând ambele modalități de abordare și scriere a sursei și modalități de tranziție.

=== "Recursiv"

Pentru a găsi soluția optimă, noi vom avea vectorul dp care se utilizează pentru memoizare, el având forma următoare: dp[suma de bani rămasă de acoperit] = numărul de bacnote necesare pentru a ajunge la suma de bani rămasă de acoperit curentă.

Pentru asta ne vom utiliza de o recursie care are ca parametri de stare suma de bani care a rămas de plătit, numărul de monede pe care l-am utilizat până acum și vectorul de denominații accesibile.

--8 < --"usor/dp/moneda_rec.cpp"

=== "Iterativ"

Pentru a găsi soluția optimă, noi vom trece prin fiecare sumă de bani care este mai mică decât $S$, încercând, dacă putem, să continuăm să adăugăm bacnote astfel încât să ajungem la suma de bani dorită. Pentru acest lucru vom ține un vector dp de forma următoare: dp[sumă de bani totală] = numărul de bacnote necesare pentru a ajunge la această sumă de bani.

--8 < --"usor/dp/moneda_iter.cpp"

Problema Vacation

View Problem

AtCoder

Deschide

Pentru această problemă, trebuie să aflăm satisfacția maximă pe care o poate obține Taro în $n$ zile, dacă nu are voie să repete o activitate de două ori la rând.

Din nou, se poate demonstra cu ușurință că o soluție de tip Greedy nu va merge, deoarece ne putem bloca alegeri mai bune ulterior cu alegerile curente.

Totodată, mai apare un element nou în rezolvarea acestor probleme, și anume faptul că vom avea nevoie de o nouă dimensiune pentru a păstra informații cu privire la ultima activitate efectuată de el, pentru a evita o situație în care alegem de două ori aceeași activitate.

Astfel, vom defini $dp\_{i,j}$ ca fiind suma maximă a satisfacției dacă am parcurs primele $i$ zile, iar ultima activitate a fost de tipul $j$, $j$ fiind 0, 1 sau 2, în funcție de activitatea aleasă.

Pentru a calcula $dp\_{i,j}$, va trebui să ne raportăm la sumele din ziua precedentă, corespunzătoare celorlalte două activități deoarece nu avem voie să alegem aceeași activitate iar.

Din nou ca la celelalte probleme, puteți găsi mai jos abordarea recursivă și cea iterativă a problemei.

=== "Recursiv"

--8 < --"usor/dp/vacation_rec.cpp"

=== "Iterativ"

--8 < --"usor/dp/vacation_iter.cpp"

=== "Iterativ optimizat"

--8 < --"usor/dp/vacation_iter_optim.cpp"

Deoarece avem nevoie doar de ultimele două linii, nu vom ține toată matricea, mutând mereu valorile calculate pe prima linie pentru a păstra corectitudinea recurenței.

Problema Array Description

View Problem

CSES

Deschide

Pentru această problemă, trebuie să aflăm numărul de șiruri pe care le putem construi astfel încât să respecte condițiile din enunț cu privire la valorile deja setate și la diferența dintre ele.

Astfel, vom defini $dp\_{i,j}$ ca fiind numărul de moduri de a crea un șir cu $i$ numere, dacă valoarea de pe poziția $i$ este $j$.

Pentru a afla $dp\_{i,j}$, va trebui să ne raportăm la valorile de pe poziția precedentă, aflate la o distanță de cel mult 1, cu condiția să putem pune $j$ pe poziția $i$.

--8 < --"usor/dp/array_description.cpp"

Problema Grid 1

View Problem

AtCoder

Deschide

Pentru această problemă, trebuie să aflăm numărul de moduri de a parcurge matricea din colțul stânga-sus în colțul dreapta-jos prin mișcări în jos și la dreapta, fără să parcurgem pătrate acoperite de ziduri.

Deoarece avem de-a face cu o matrice, putem ține $dp\_{i,j}$ ca fiind numărul de moduri de a parcurge matricea dacă am ajuns la pătratul $(i, j)$. Deoarece putem ajunge la $(i, j)$ din pătratele de sus și stânga, acestea vor fi cele două rezultate care contribuie la răspunsul dat.

Astfel, $dp\_{i,j} = dp\_{i-1,j} + dp\_{i,j-1}$.

Soluție

--8 < --"usor/dp/grid1.cpp"

Problema Sumtri1

View Problem

PBInfo

Deschide

=== "Recursiv"

--8 < --"usor/dp/sumtri1_rec.cpp"

=== "Iterativ"

--8 < --"usor/dp/sumtri1_iter.cpp"

Probleme suplimentare

• Infoarena custi
• Codeforces Boredom
• AtCoder Weak Takahashi
• IIOT 2023-24 PingPong
• AtCoder 1111gal password
• AtCoder Flip Cards
• IIOT Police
• Counting Towers
• AtCoder Index × A(Not Continuous ver.)
• AtCoder Between Two Arrays
• Lot Juniori Minusk
• AtCoder Count Bracket Sequences
• AtCoder I hate Non Integer Number
• Not Escaping Codeforces
• Problemele cu DP de pe Kilonova
• Problemele intre rating 500 si 1400 de aici
• Problemele cu DP de pe infoarena

Resurse suplimentare

• DP Book
• Programare dinamica - CPPI Sync
• Introduction to DP - USACO Guide
• Dynamic Programming Prologue - Codeforces
• Simple DP Optimizations - Codeforces
• DP Tutorial and Problem List