De ce contează?
Pleci în excursie și pui obiecte în rucsac. Câteodată e destul să ții minte un singur număr — „câte kilograme am pus". Dar dacă fiecare oraș vizitat își are biletul lui, întrebarea „pot continua de aici?" nu mai depinde de câte orașe ai văzut, ci de exact care. „Trei orașe vizitate" nu spune nimic: contează dacă ai fost în Cluj sau în Iași. Atunci memoria ta nu mai e un număr — e ÎNTREAGA listă de orașe bifate.
Intuiția
La DP-ul clasic, starea e compactă: un indice, o sumă, o lungime — „trecutul"
se rezumă la un singur număr. Există însă probleme unde viitorul depinde de
exact ce submulțime de elemente ai folosit până acum, nu doar de câte.
Acolo nu mai poți comprima trecutul: starea devine o submulțime, iar un set
de n elemente are 2^n submulțimi.
Declicul de modelare: când ce ai folosit contează, dar ordinea în care
ai folosit NU, toate cele n! ordini se comasează în doar 2^n submulțimi.
Exponențial sună rău — dar e enorm mai puțin decât factorial: la n = 20,
2^20 ≈ 10^6 față de 20! ≈ 2,4·10^18. DP-ul pe submulțimi e exact această
comasare.
Cum se codifică o submulțime pe biți și cum se scriu tranzițiile — asta
aprofundezi în lecția următoare, DP cu bitmask. Aici antrenăm pasul de
dinainte, cel mai valoros: să recunoști că starea trebuie să fie o
submulțime și să verifici că 2^n încape în timp și memorie.