Metoda greedy și programarea dinamică

Metode de programare — metoda greedy și elemente de programare dinamică

Aplicarea metodei greedy la problema spectacolelor și la problema restului, cu justificarea criteriului de alegere.
Scrierea și completarea recurențelor de programare dinamică pentru subșirul crescător maximal, suma maximă a unei subsecvențe și numărarea drumurilor.
Alegerea metodei potrivite pentru o cerință dată și estimarea complexității rezolvării.

Greedy alege la fiecare pas cea mai bună variantă locală și nu revine asupra ei; este rapid, dar corect numai când alegerea locală poate fi demonstrată optimă.
La problema spectacolelor, criteriul corect este sortarea crescătoare după ora de sfârșit.
La problema restului, greedy funcționează pentru sistemele obișnuite de monede, dar nu pentru orice sistem: cu monedele 1, 3 și 4 și suma 6 dă trei monede în loc de două.
Programarea dinamică se aplică problemelor cu substructură optimă și subprobleme suprapuse; fiecare subproblemă se rezolvă o singură dată și se păstrează într-un tablou.
Subșir crescător maximal: best[i] = 1 + max(best[j]) pentru j < i cu v[j] < v[i], complexitate O(n^2).
Suma maximă a unei subsecvențe: s[i] = max(s[i - 1] + v[i], v[i]), complexitate O(n).
Numărarea drumurilor într-o grilă: d[i][j] = d[i - 1][j] + d[i][j - 1], cu prima linie și prima coloană egale cu 1.
Subșirul nu cere elemente alăturate; subsecvența le cere.