Question

Salut !
Puteti sa-mi dati 2 asemanarii intre divide et Impera si programare dinamica si 2 asemanarii pt backtracking si greedy

Answer 1

► 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