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

IndexError: list index out of range la dp[n] (tabelul DP e prea scurt)

Pe scurt

Ai creat tabelul cu dp = [0] * n, dar răspunsul e dp[n], iar o listă cu n elemente are doar indicii 0..n-1. Când dp[i] înseamnă „primele i elemente” sau „treapta i”, tabelul are nevoie de n + 1 poziții: dp = [0] * (n + 1).

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

Ce înseamnă

Multe probleme DP definesc dp[i] ca răspunsul pentru primele i elemente sau pentru valoarea i (suma i, treapta i, lungimea i). Atunci i merge de la 0 (cazul vid) la n (toată intrarea), adică n + 1 valori. Dacă inițializezi dp = [0] * n, ultima poziție, chiar cea cu răspunsul, lipsește.

Eroarea apare de obicei la return dp[n] sau în ultima iterație a buclei. Alteori apare la cazurile de bază: dp[1] = 1 pe un tabel cu o singură poziție (n = 0 sau n = 1), adică exact cazurile limită din teste.

Înainte de cod, scrie în cuvinte ce înseamnă dp[i] și care e intervalul lui i. Dimensiunea tabelului reiese direct din această definiție.

De ce apare: cauzele frecvente

1Tabelul are n poziții în loc de n + 1

Greșit
PYTHON
dp = [0] * n
dp[0] = 1
for i in range(1, n + 1):
    dp[i] = dp[i - 1] * 2
return dp[n]
Corect
PYTHON
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    dp[i] = dp[i - 1] * 2
return dp[n]

Cu n + 1 poziții, indicii 0..n există toți, iar dp[n] este răspunsul pentru toată intrarea.

2Cazurile de bază pe un tabel prea mic

Greșit
PYTHON
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
Corect
PYTHON
dp = [0] * (n + 1)
dp[0] = 1
if n >= 1:
    dp[1] = 1

Pentru n = 0 tabelul are o singură poziție, deci dp[1] nu există. Alternativ, creează tabelul cu max(n + 1, 2) poziții.

3Rucsac / monede: tabelul după sumă

Greșit
PYTHON
dp = [0] * suma
dp[0] = 1
for m in monede:
    for s in range(m, suma + 1):
        dp[s] += dp[s - m]
Corect
PYTHON
dp = [0] * (suma + 1)
dp[0] = 1
for m in monede:
    for s in range(m, suma + 1):
        dp[s] += dp[s - m]

Indicele este chiar suma, de la 0 la suma, deci ai nevoie de suma + 1 poziții.

Repară tu

Repară eroarea, direct în pagină

Funcția moduri_plata(suma, monede) numără în câte moduri poți plăti exact suma cu monedele date (ordinea nu contează), cu DP de jos în sus. Codul dă IndexError: list index out of range. Repar-o ca să afișeze 4, 1 și 0.

Codul care dă eroarea
PYTHON
def moduri_plata(suma, monede):
    dp = [0] * suma
    dp[0] = 1
    for m in monede:
        for s in range(m, suma + 1):
            dp[s] += dp[s - m]
    return dp[suma]

print(moduri_plata(5, [1, 2, 5]))
print(moduri_plata(0, [1, 2]))
print(moduri_plata(3, [2]))
După reparație, programul afișează
4
1
0
Indiciu

Indicele tabelului este chiar suma, de la 0 la suma inclusiv.

Alte forme ale mesajului

  • IndexError: list index out of range

Cum o eviți pe viitor

Scrie definiția într-un comentariu: # dp[i] = numărul de moduri pentru primele i trepte, i = 0..n. Din „i = 0..n” rezultă [0] * (n + 1). Testează funcția pe n = 0 și n = 1 înainte de exemplul mare: acolo pică de obicei cazurile de bază scrise pe poziții care nu există.

Întrebări frecvente

De ce DP-ul are nevoie de poziția 0?

Poziția 0 reprezintă cazul vid (zero elemente, suma 0, nicio treaptă) și e baza recurenței. Fără ea, primul pas ar trebui tratat separat.

Pot evita complet tabelul?

Când recurența folosește doar ultimele una-două valori (scări, Fibonacci, case alăturate), poți păstra doar acele variabile. Dar varianta cu tabel e mai ușor de verificat la început.

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.