De ce contează?
Mergi pe un traseu montan și vrei să știi câte cărări duc la fiecare refugiu. N-ai nevoie să-ți amintești fiecare pas, fiecare poză făcută pe drum și fiecare pauză de apă — ar fi un jurnal infinit. Îți ajunge un singur număr scris pe ușa fiecărui refugiu: „câte cărări ajung aici". Acel număr e tot ce-ți trebuie ca să-l afli pe următorul. Asta e o stare în programarea dinamică.
Intuiția
O stare este informația minimă care identifică unic o subproblemă. În DP
pe prefixe scriem aproape mereu dp[i] = răspunsul pentru „primele i elemente"
sau „prefixul până la poziția i". Cheia: starea nu reține cum ai ajuns acolo,
ci doar răspunsul deja calculat pentru acea bucată. Restul se reconstruiește
din tranziție.