De ce contează?
Joci un joc lung pe telefon și trebuie să-l închizi brusc. Ce notezi pe un bilet ca să poți relua exact de unde ai rămas? Nu rejoci toată partida în minte — scrii doar atât cât îți trebuie: nivelul, viața rămasă, ce ai în inventar. Nici mai mult, nici mai puțin. Alegerea stării într-un DP este exact acest bilet: cea mai mică informație din care poți continua decizia.
Ideea-cheie
În programarea dinamică, partea grea aproape niciodată nu e formula finală. E o singură întrebare, pusă înainte de orice cod: ce trebuie să știu despre o subproblemă ca să iau decizia următoare? Răspunsul la întrebare este starea.
Gândește-te la o decizie pe care o iei acum — iei sau nu un obiect, mergi în jos sau în dreapta, păstrezi sau sari un element. După ce ai decis, ai ajuns într-o subproblemă mai mică. Întrebarea-test e: ce date despre subproblema rămasă îmi sunt absolut necesare ca să continui? Tot ce nu intră în acel răspuns nu aparține stării.
Starea = informația minimă suficientă pentru a continua. „Suficientă" înseamnă că din ea poți face tranziția (pasul către subproblema următoare). „Minimă" înseamnă că dacă scoți orice bucată, tranziția nu mai poate fi calculată. Două întrebări o fixează: „ce decid acum?" și „ce trebuie să știu pentru decizia următoare?".