Suma maximă fără elemente vecine
Un curier livrează pe o stradă cu case așezate în linie. Fiecare casă îi oferă un bacșiș, dar regula firmei spune că nu poate livra la două case vecine în aceeași tură. Care este bacșișul maxim pe care îl poate strânge? E o problemă clasică de DP, cu o decizie la fiecare pas: iei sau sari.
Problema și de ce greedy nu merge
Primești lista bacsis. Alegi o submulțime de case, fără două alăturate, cu suma maximă.
Scrie suma_neadiacenta(lista) (suma maximă fără două elemente vecine) și circulara(lista) (aceeași problemă, dar prima și ultima poziție sunt vecine). Folosește programarea dinamică, nu toate submulțimile. Testele sunt deja scrise.
- În suma_neadiacenta, la fiecare element alege între „sari” și „iei” cu max.
- În circulara, tratează lista cu un element, apoi apelează suma_neadiacenta fără ultimul și fără primul element.
- Trebuie să apară: 4, 12, 4, 3.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan