► Asemanari divide & impera - programare dinamica
- Problema initiala se imparte in subprobleme asemanatoare de dimensiune mai mica.
- Problemele rezolvate au proprietatea de substructura optima.
► Asemanari programare dinamica - greedy
- Solutie este construita in maniera bottom-up de la un caz simplu pana la cazul complex
- Construirea solutiei pentru cazul de dimensiune n+1 se realizeaza folosind solutia (solutiile in cazul programarii dinamice) pentru cazul de dimensiune n, astfel rezolvarea optima a problemei depinde de rezolvarea optima a subproblemei/subproblemelor.
- Se aplica problemelor de optimizare in care se urmareste determinarea unei solutii optime
- Atat programarea dinamica cat si greedy pot fi folosite atunci cand solutia unei probleme poate fi privita ca rezultatul unei secvente de decizii
