Python de la zero

2. Ce este programarea dinamică?

Două idei esențiale

Programarea dinamică nu este o comandă Python. Este o tehnică algoritmică.

3. Cum definim o stare?

O stare descrie exact informația de care avem nevoie pentru a ști ce rezultat trebuie calculat.

Exemplu: Fibonacci

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2)

Pentru F(5), apar subproblemele F(4) și F(3). Fără memorare, unele valori sunt recalculate.

4. Memoizarea — de sus în jos

Putem păstra rezultatele deja calculate într-o listă.

def fib(n, mem):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if mem[n] != -1:
        return mem[n]

    mem[n] = fib(n - 1, mem) + fib(n - 2, mem)
    return mem[n]

n = int(input())
mem = [-1] * (n + 1)
print(fib(n, mem))

Observăm legătura cu Partea 5: recursivitatea rămâne, dar rezultatele sunt memorate.

5. Bottom-up — construim de la mic la mare

În loc să pornim de la problema mare, calculăm mai întâi cazurile mici și apoi construim rezultatul.

n = int(input())
dp = [0] * (n + 1)

if n >= 1:
    dp[1] = 1

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])

Ce conține dp[i]?

dp[i] reprezintă valoarea problemei pentru starea i. Aceasta este o convenție pe care noi o alegem pentru problemă.

6. Probleme pe șiruri

Programarea dinamică poate fi folosită pentru probleme în care construim un răspuns pe prefixe ale unui șir.

Exemplu: cea mai lungă subsecvență crescătoare — idee simplificată

Definim dp[i] ca lungimea celei mai lungi subsecvențe crescătoare care se termină la poziția i.

a = [3, 1, 2, 5, 4]
n = len(a)
dp = [1] * n

for i in range(n):
    for j in range(i):
        if a[j] < a[i] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1

print(max(dp))

7. Programare dinamică pe grile

O matrice poate reprezenta o grilă. Putem calcula numărul de moduri de a ajunge într-o celulă folosind celulele anterioare.

Exemplu: drumuri într-o grilă fără obstacole

n = int(input())
m = int(input())

dp = [[0] * m for i in range(n)]
dp[0][0] = 1

for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            continue
        if i > 0:
            dp[i][j] = dp[i][j] + dp[i - 1][j]
        if j > 0:
            dp[i][j] = dp[i][j] + dp[i][j - 1]

print(dp[n - 1][m - 1])

La fiecare celulă, putem veni de sus sau din stânga. De aceea rezultatul este suma celor două rezultate precedente.

8. Problema rucsacului — introducere

Avem obiecte cu greutăți și valori. Rucsacul are o capacitate limitată. Dorim să alegem obiecte astfel încât valoarea totală să fie cât mai mare.

Pentru început, definim:

dp[i][c] = valoarea maximă obținută folosind primele i obiecte și o capacitate c.

Decizia

Pentru obiectul curent avem două posibilități:

1. Nu îl alegem.
2. Îl alegem, dacă încape.

if greutate[i - 1] <= c:
    dp[i][c] = max(
        dp[i - 1][c],
        valoare[i - 1] + dp[i - 1][c - greutate[i - 1]]
    )
else:
    dp[i][c] = dp[i - 1][c]

Aici max() compară cele două decizii posibile.

9. Nu vrem întotdeauna doar valoarea

Uneori problema cere nu doar „care este valoarea optimă?”, ci și ce alegeri au produs-o.

În acest caz putem porni de la starea finală și să mergem înapoi, identificând deciziile care au fost luate.

10. De ce este mai eficient?

Un algoritm recursiv fără memorare poate calcula aceeași subproblemă de foarte multe ori. Prin memorare, fiecare stare poate fi calculată o singură dată.

Complexitatea exactă depinde de problemă și de numărul de stări și tranziții.

11. Cum recunoaștem o problemă de programare dinamică?

Dacă răspunsul este „da” la aceste întrebări, merită să investigăm o soluție de programare dinamică.

12. Exerciții rezolvate

n = int(input())
if n == 0:
    print(0)
else:
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])

13. Exerciții propuse

14. Greșeli frecvente

• Definirea unei stări care nu conține informația necesară.
• Folosirea unei tranziții greșite.
• Uitarea cazurilor de bază.
• Dimensiune insuficientă pentru lista sau matricea dp.
• Confundarea „numărului de soluții” cu „valoarea optimă”.
• Calcularea corectă a valorii, dar fără a ști cum se reconstruiește soluția când problema o cere.

15. Checklist final