De ce contează?
Imaginează-ți un rând de n becuri, câte unul pentru fiecare oraș. Becul aprins
înseamnă „orașul ăsta l-am vizitat deja", becul stins înseamnă „încă nu". Tot
acest rând de aprins/stins e, de fapt, un singur număr scris în binar. Nu mai
ții minte ordinea în care ai trecut prin orașe — ții minte doar care becuri
sunt aprinse. Aceasta e ideea care transformă un calcul imposibil într-unul
rapid.
Intuiția
Vrei drumul cel mai ieftin care trece exact o dată prin toate cele n orașe
(problema comis-voiajorului, TSP). Cheia tehnicii bitmask: o mulțime de orașe
vizitate o codifici ca un număr. Becul i aprins = bitul i din număr este
1. Astfel mulțimea devine numărul binar 101 = 5. Acum „starea" în
care te afli nu mai e o listă, ci un întreg pe care îl poți folosi ca index în
tablou.
Declicul central: submulțimea devine indice de tablou. „Pe cine am folosit
deja" părea o stare imposibil de indexat — dar scrisă ca număr pe n biți e
doar un indice între 0 și 2^n - 1. Când scrii dp[5], indexezi de fapt cu
mulțimea {0, 2}.