...
Programare dinamică

Programare dinamică: ce este și cum o folosești

Pe scurt

Programarea dinamică este o metodă prin care rezolvi o problemă mare din răspunsurile unor probleme mai mici de același fel, pe care le calculezi o singură dată și le ții minte. Funcționează când aceleași subprobleme apar de mai multe ori: în loc să le recalculezi, iei rezultatul din tabel. Așa, probleme care ar dura ani încercând toate variantele se rezolvă într-o fracțiune de secundă.

  • 2condiții: subprobleme suprapuse și substructură optimă
  • 2moduri: memoizare și tabulare
  • O(n)pentru scări, față de O(2ⁿ) recursiv
  • 2lecții gratuite, fără card
PROGRAMARE DINAMICĂ dp[0] 1 dp[1] 1 dp[2] 2 dp[3] 3 dp[4] 5 dp[5] 8 dp[6] 13 dp[6] = dp[5] + dp[4] = 8 + 5 = 13 O(n) memo · tabel

Tabelul de programare dinamică, în animație

Problema: în câte feluri urci n trepte, dacă faci pași de 1 sau 2? Fiecare celulă se calculează din cele două dinaintea ei. Sus vezi câte apeluri ar face varianta recursivă fără memorare.

Ideea, pe exemplul scărilor

Ca să ajungi pe treapta n, ultimul pas a fost fie de 1 (de pe treapta n-1), fie de 2 (de pe treapta n-2). Deci numărul de moduri este dp[n] = dp[n-1] + dp[n-2], cu dp[0] = dp[1] = 1. Aceasta este relația de recurență, inima oricărei soluții de programare dinamică.

Scrisă direct recursiv, funcția calculează aceleași valori de foarte multe ori: pentru n = 40 face peste 300 de milioane de apeluri. Cu un tabel, fiecare valoare se calculează o dată: 40 de pași.

Pașii pentru orice problemă: 1) definești ce înseamnă dp[i] în cuvinte; 2) găsești recurența; 3) stabilești cazurile de bază; 4) alegi ordinea de calcul; 5) iei răspunsul din tabel.

Programare dinamică în C++, Python și Java

Varianta cu tabel (tabulare, de jos în sus) și varianta recursivă cu memorare (memoizare, de sus în jos).

def moduri(n):
    """În câte feluri urci n trepte, cu pași de 1 sau 2?"""
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # ultimul pas: de 1 sau de 2
    return dp[n]


print(moduri(5))    # 8
print(moduri(50))   # 20365011074, instant

Încearcă: costul minim pe scări, cu tabel

Problema din lecția 127 a cursului de algoritmi: aceeași idee ca la numărarea modurilor, dar cu minim în loc de sumă.

Exercițiu din lecția 127 · cursul de algoritmi

Tabulare vs memoizare: costul minim pe scări

Scrie funcția cost_minim(cost) care returnează costul minim până la vârful scării, în varianta tabelară (bottom-up), fără recursivitate. Pentru punctaj maxim, folosește doar două variabile (O(1) spațiu). Testele sunt deja scrise.

  1. Pornește cu două variabile egale cu 0 (costul de a ajunge pe treptele 0 și 1).
  2. Pentru fiecare poziție de la 2 la len(cost), calculează minimul dintre cele două variante.
  3. Glisează variabilele și returnează ultima valoare. Trebuie să apară: 15, 6, 0.
Indiciu: Pentru [0, 0] poți porni direct de pe treapta 1 și sări pe vârf: costul este 0.
def cost_minim(cost):
    doi_inainte, unu_inainte = 0, 0
    for i in range(2, len(cost) + 1):
        curent = min(unu_inainte + cost[i - 1], doi_inainte + cost[i - 2])
        doi_inainte, unu_inainte = unu_inainte, curent
    return unu_inainte


print(cost_minim([10, 15, 20]))
print(cost_minim([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
print(cost_minim([0, 0]))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Memoizare sau tabulare?

Memoizare (top-down)Tabulare (bottom-up)
Cum aratăfuncție recursivă + dicționar / cachebucle care completează un tablou
Ce calculeazădoar subproblemele de care e nevoietoate subproblemele, în ordine
Avantajse scrie ușor pornind de la recurențăfără risc de stack overflow, des mai rapidă
Memorietabel + stiva de apeluritabel; uneori se reduce la câteva variabile

Probleme clasice de programare dinamică

ProblemăCe înseamnă dpComplexitate
Urcarea scărilor / Fibonaccidp[i] = moduri de a ajunge pe treapta iO(n)
Restul cu număr minim de monededp[s] = monede minime pentru suma sO(n · S)
Problema rucsacului (0/1)dp[i][g] = valoarea maximă cu primele i obiecte și greutatea gO(n · G)
Cel mai lung subșir comundp[i][j] = lungimea pentru prefixele de lungime i și jO(n · m)
Subsecvența de sumă maximădp[i] = suma maximă care se termină la iO(n)
Drumul de cost minim într-o matricedp[i][j] = costul minim până la celula (i, j)O(n · m)

Dacă la fiecare pas poți alege sigur varianta cea mai bună fără să te uiți înapoi, ajunge un algoritm greedy. Cum le deosebești vezi în lecția greedy vs programare dinamică.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Super usor de inteles. Cursurile de programare video onlinesunt foarte bine explicate

Fotografia lui Laura Chiriazi, cursant al Academiei ProgramatorilorLaura ChiriaziRecenzie pe Google

Recomand, lecțiile sunt explicate pe întelesul cursantului si pe langa asta practica este compusă din exerciții din care inveti sa programezi!

Fotografia lui Ioan John, cursant al Academiei ProgramatorilorIoan JohnRecenzie pe Google

Am achiziționat pachetul de 36 de ședințe individuale pentru cursul de Java, avându-l ca instructor pe Tudor. Cursul este foarte bine structurat și este plin de exemple din viața cotidiană, aspect care îl face ușor de înțeles. De asemenea, Tudor a dat dovadă de profesionalism și răbdare pe parcursul ședințelor prin faptul că explică materia până în momentul în care înțelegi. Recomand cu căldură cursurile susținute de Tudor.

Fotografia lui Alexandru, cursant al Academiei ProgramatorilorAlexandruRecenzie pe Google

Întrebări frecvente

Ce este programarea dinamică?

Programarea dinamică este o metodă de rezolvare a problemelor care împarte problema în subprobleme mai mici de același tip, rezolvă fiecare subproblemă o singură dată și îi reține rezultatul, astfel încât să nu fie recalculat. Se folosește mai ales la probleme de optimizare și de numărare.

Când se folosește programarea dinamică?

Când problema are subprobleme suprapuse (aceleași calcule apar de mai multe ori) și substructură optimă (soluția optimă se construiește din soluțiile optime ale subproblemelor). Indicii frecvente: „în câte moduri”, „minimul / maximul posibil”, „cel mai lung / scurt”.

Care e diferența dintre memoizare și tabulare?

Memoizarea este varianta de sus în jos: scrii funcția recursivă și reții rezultatele deja calculate. Tabularea este varianta de jos în sus: completezi un tabel cu bucle, pornind de la cazurile de bază. Ambele au aceeași complexitate.

Care e diferența dintre programare dinamică și greedy?

Un algoritm greedy alege la fiecare pas varianta care pare cea mai bună în acel moment și nu revine asupra deciziei. Programarea dinamică ia în calcul toate variantele prin subprobleme. Greedy e mai simplu, dar dă soluția optimă doar pentru anumite probleme.

Care e diferența dintre programare dinamică și divide et impera?

Ambele împart problema în subprobleme. La divide et impera subproblemele sunt independente (ca la merge sort), deci nu are rost să le reții. La programarea dinamică subproblemele se repetă, așa că le reții rezultatele.

Unde exersez programarea dinamică?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai lecții de programare dinamică de la urcarea scărilor până la probleme de interviu, cu cod Python verificat automat în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.