Greedy sau programare dinamică?
Ai văzut că greedy („alege mereu ce pare cel mai bun acum”) greșește la monede și la rucsac. Totuși, pentru unele probleme greedy este corect și mult mai simplu decât DP. La interviu, întrebarea importantă nu e „ce algoritm știu?”, ci „pot demonstra că alegerea locală e și optimă global?”.
Ce înseamnă greedy
Un algoritm greedy (lacom) ia la fiecare pas decizia care pare cea mai bună în acel moment și nu revine asupra ei. Programarea dinamică, în schimb, ia în calcul toate variantele subproblemelor și le combină.
Scrie poti_ajunge(sarituri) (greedy cu poziția maximă accesibilă, O(n)) și activitati_maxime(intervale) (greedy după cel mai devreme sfârșit; o activitate poate începe exact când se termină alta). Testele sunt deja scrise.
- În poti_ajunge, ține cel_mai_departe și returnează False dacă poziția curentă îl depășește.
- În activitati_maxime, sortează după sfârșit (key=lambda x: x[1]) și numără activitățile compatibile.
- Trebuie să apară: True, False, True, 4, 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan