...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

Memo greșit: cheia nu conține toți parametrii, iar rezultatul e greșit

Pe scurt

Ai salvat în memo rezultatul doar după i (memo[i]), dar funcția depinde și de alt parametru (capacitate, j, suma rămasă), așa că un rezultat calculat pentru o stare e refolosit pentru alta. Cheia memo-ului trebuie să conțină toți parametrii care schimbă rezultatul: memo[(i, capacitate)].

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Memoizarea e corectă doar dacă rezultatul funcției depinde numai de cheia memo-ului. Dacă funcția are doi parametri care se schimbă (i și capacitate, i și j, poziția și suma rămasă), iar tu salvezi doar memo[i], primul rezultat calculat pentru un i va fi refolosit pentru orice altă capacitate. Python nu dă nicio eroare: rezultatul e pur și simplu greșit, de obicei doar pe unele teste.

O variantă înrudită: un memo global, păstrat între apelurile pentru intrări diferite. Al doilea test primește rezultatele primului. Cu @lru_cache această problemă nu apare pentru argumente, pentru că toți parametrii fac parte automat din cheie, dar apare dacă funcția citește o variabilă globală care se schimbă.

În „Repară tu” testele folosesc assert, deci vezi AssertionError cu valoarea greșită.

De ce apare: cauzele frecvente

1Cheia ignoră un parametru

Greșit
PYTHON
def rucsac(i, cap):
    if i == len(greutati) or cap == 0:
        return 0
    if i in memo:
        return memo[i]
    best = rucsac(i + 1, cap)
    if greutati[i] <= cap:
        best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
    memo[i] = best
    return best
Corect
PYTHON
def rucsac(i, cap):
    if i == len(greutati) or cap == 0:
        return 0
    if (i, cap) in memo:
        return memo[(i, cap)]
    best = rucsac(i + 1, cap)
    if greutati[i] <= cap:
        best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
    memo[(i, cap)] = best
    return best

Rezultatul pentru produsul i depinde de capacitatea rămasă. Tuplul (i, cap) face ca fiecare stare să aibă propria intrare în memo.

2Memo global refolosit pentru alte date

Greșit
PYTHON
memo = {}
def drumuri(n):
    ...

print(drumuri_pe_harta(harta1))
print(drumuri_pe_harta(harta2))
Corect
PYTHON
def drumuri_pe_harta(harta):
    memo = {}
    def drumuri(r, c):
        ...
    return drumuri(0, 0)

Memo-ul creat în funcția exterioară e nou pentru fiecare hartă, deci rezultatele nu se amestecă între teste.

Repară tu

Repară eroarea, direct în pagină

Funcția valoare_maxima(greutati, valori, capacitate) rezolvă problema rucsacului (fiecare produs o singură dată) cu memoizare, dar testele cu assert pică: memo-ul ține minte rezultatul doar după indicele produsului. Repar-o ca testele să treacă și să afișeze 9, 0 și 10.

Codul care dă eroarea
PYTHON
def valoare_maxima(greutati, valori, capacitate):
    memo = {}
    def rucsac(i, cap):
        if i == len(greutati):
            return 0
        if i in memo:
            return memo[i]
        best = rucsac(i + 1, cap)
        if greutati[i] <= cap:
            best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
        memo[i] = best
        return best
    return rucsac(0, capacitate)

r = (valoare_maxima([1, 3, 4], [1, 4, 5], 7), valoare_maxima([5], [10], 4), valoare_maxima([5], [10], 5))
assert r == (9, 0, 10), f"memo gresit: {r}"
print(*r)
După reparație, programul afișează
9 0 10
Indiciu

Rezultatul depinde atât de produsul curent, cât și de capacitatea rămasă.

Cum o eviți pe viitor

Înainte să adaugi memoizarea, scrie starea subproblemei: ce parametri determină complet răspunsul? Toți aceștia intră în cheie, ca tuplu. Variabilele care nu se schimbă (lista de intrare) nu intră în cheie, dar memo-ul trebuie creat din nou pentru fiecare intrare. Cel mai sigur: @lru_cache pe o funcție interioară, care include automat toți parametrii.

Întrebări frecvente

De ce primul test trece și al doilea nu?

La primul apel memo-ul e gol, deci rezultatele sunt calculate corect pentru stările întâlnite primele. Problemele apar când o stare nouă are aceeași cheie incompletă ca una veche, sau când memo-ul păstrează rezultate de la alt test.

Cum găsesc parametrii care trebuie să fie în cheie?

Uită-te la apelurile recursive: orice argument care diferă de la un apel la altul (nu doar i) face parte din stare. Dacă funcția citește o variabilă din afară care se schimbă, și aceea face parte din stare.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.