IndexError: list index out of range la dp[n] (tabelul DP e prea 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
dp = [0] * n
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] * 2
return dp[n]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
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1dp = [0] * (n + 1)
dp[0] = 1
if n >= 1:
dp[1] = 1Pentru 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ă
dp = [0] * suma
dp[0] = 1
for m in monede:
for s in range(m, suma + 1):
dp[s] += dp[s - m]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ă 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.
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]))4 1 0
Indiciu
Indicele tabelului este chiar suma, de la 0 la suma inclusiv.
Reparația
def moduri_plata(suma, monede):
dp = [0] * (suma + 1)
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]))De ce merge
dp[s] este numărul de moduri de a plăti suma s, pentru s de la 0 la suma, deci tabelul are nevoie de suma + 1 poziții. Cu [0] * suma, pentru suma 5 nu exista dp[5], iar pentru suma 0 nu exista nici dp[0]. dp[0] = 1 înseamnă că suma 0 se plătește într-un singur fel: fără nicio monedă. Parcurgerea monedelor în bucla exterioară numără combinațiile, nu ordinile: pentru 5 sunt 4 (5, 2+2+1, 2+1+1+1, 1×5).
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
TypeError: 'int' object is not subscriptable la dp[i][j] Ai creat tabelul DP cu o singură dimensiune (dp = [0] * n), deci dp[i] este un număr, iar dp[i][j] încearcă să ia un element dintr-un număr. Creează o matrice: dp = [[0] * coloane for _ in range(randuri)]. IndexError: list index out of range la un graf cu noduri numerotate de la 1 Nodurile sunt numerotate de la 1 la n, dar lista de adiacență are n poziții (0..n-1), așa că graf[n] nu există. Creează n + 1 liste: graf = [[] for _ in range(n + 1)], și ignoră poziția 0. Recursivitatea fără memoizare rulează la nesfârșit: fib(40) nu se mai termină Funcția recursivă recalculează aceleași subprobleme de un număr exponențial de ori (fib(40) face sute de milioane de apeluri), așa că pare blocată și editorul o oprește după limita de timp. Salvează rezultatele: @lru_cache(maxsize=None) sau un dicționar memo. Î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.
