De ce contează?
Cheia oricărui DP nu e codul — e o singură întrebare: „care e STAREA?". Gândește-te la un drumeț care notează pe un bilețel exact ce trebuie să-și amintească dintr-un oraș ca să continue drumul: nu tot ce a văzut, ci fix cât îi trebuie pentru deciziile de aici încolo. Acel bilețel minimal e starea. Dacă scrii pe el prea puțin, te rătăcești; dacă scrii prea mult, cari un bagaj inutil. Toată arta DP-ului e să afli ce trebuie scris pe bilețel.
Ideea-cheie
Când te blochezi la o problemă de DP, instinctul e să te apuci de cod: tablouri, bucle, formule. Greșit. Codul e ultimul pas. Mai întâi modelezi — adică decizi ce înseamnă o subproblemă și cum se leagă subproblemele între ele. Odată ce starea e bine aleasă, recurența aproape se scrie singură, iar codul devine o transcriere mecanică.
Modelarea nu e despre algoritm nou. E despre a recunoaște că problema din fața ta este un DP și a-i da forma corectă. Aceeași întrebare („care e starea?") deschide și un șir, și un arbore, și o submulțime — doar răspunsul diferă.
Starea corectă = minimul de informație care face viitorul independent de CUM ai ajuns aici. Testul decisiv: dacă două „drumuri" diferite prin problemă ajung în situații cu exact același viitor posibil, ele sunt aceeași stare — a le ține separate înseamnă muncă dublă degeaba.
De aici, modelarea răspunde la trei întrebări, în ordine:
- CE descrie complet o subproblemă? — starea: setul minim din care poți decide mai departe fără să te uiți în trecut.
- Cum se compune din stări mai mici? — recurența.
- În ce ORDINE le calculez? — astfel încât dependențele să fie gata la timp.
Dacă alegi bine starea, recurența vine singură. Aproape întotdeauna lupta e doar la prima întrebare.