TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Ausarbeitung Tests/20080131 3.A.b

sowohl bei dyn. programmierung als auch bei divide and conquer wird ein problem gelöst durch teilung des problems in leichter zu lösende teilprobleme.

bei divide and conquer kann je nach anwendung (versch. algorithmen bzw strategien) die lösung des letzten teilproblems schon zur lösung führen. oder es werden alle teillösungen zu einer gesamtlösung zusammengefügt. oder eine bestimmte teillösung ist die lösung für das gesamtproblem (siehe wikipedia). dh. das gesamtproblem wird in *bestimmte* teilprobleme aufgespalten (zb immer in der mitte, so wie bei quicksort mit pivot-element)

bei dyn. programmierung hingegen wird das gesamtproblem in kleinste teilproblem aufgespalten. diese probleme werden rekursiv abgearbeitet (also auch mehrmals verwendet).

?

Anmerk.:

Dynamische Programmierung: [...] Idee: Zerlege das Problem in kleinere Teilprobleme "Pi" ähnlich wie bei Divide and Conquer. Allerdings: während die "Pi" bei Divide and Conquer unabhängig sind, sind sie hier voneinander abhängig. Dazu: Löse jedes Teilproblem und speichere das Ergebnis "Ei" so ab, das "Ei" zur Lösung größerer Probleme verwendet werden kann.[...]

edit: Reuben Tishkoff