Мы с Milanin временами любим поспорить на тему отличия жадности и динамики. Он предпочитает большинство жадностей считать динамикой, я нет.

Что у них общего? И у того и у другого подхода решение задачи получается в результате множества этапов на каждом из которых мы получаем оптимальный ответ для какого-то состояния исходя из некоторых уже полученных оптимальных ответов для других состояний.

Что различного? В случае с динамикой мы фиксируем текущее состояние, для которого уже знаем оптимальный ответ, и рассматриваем ВСЕ способы достичь следующее. Необходимым условием является то, что следующее состояние должно быть достижимо только из уже посчитанных. Возможно на этом этапе используется жадность для того, что бы отсечь некоторые заведомо не оптимальные переходы.

В случае с жадностью мы фиксируем текущее состояние и рассматриваем для него множество всевозможных переходов, упорядоченное по некоторому критерию. Из этого множества мы всегда выбираем первый валидный переход.

Для примера рассмотрим кратчайший путь во взвешенном ориентированном графе. А именно вот в этом:

Из вершины 1 в вершину 3.

Эту задачу можно решать как дейкстрой так и динамикой. При этом дейкстра будет жадностью. Так как на каждом шаге у нас есть множество всевозможных переходов и мы не задумываясь ни о чём выбираем самый дешёвый (с учётом расстояния до вершины из которой он исходит). Мы совершенно не представляем куда можем попасть и у нас нет никаких ограничений, кроме существования перехода. Когда мы этот переход нашли, остальные нас уже не волнуют.

Если же решать задачу динамикой, то, считая ответ для вершины 3, нам необходимо уже знать ответ для вершины 2, и нам обязательно рассмотреть все способы в текущую вершину войти. В то время как жадность позволяет узнать ответ для 3, не зная ещё ответ для 2. Хотя и имея некоторые представления о нём. Для динамики обычно заранее известен порядок рассмотра вершин. Для ориентированного графа — одна из топологических сортировок. В то время как для жадности порядок рассмотра определяется самой жадностью. По крайней мере на него нельзя заранее наложить ограничения не диктуемые свойствами самой жадности.

Жадность позволяет вообще пропустить некоторые промежуточные состояния. Иногда это очень эффективно. Динамика рассматривает все возможные состояния и все возможные переходы между ними (возможно с некоторыми жадными отсечениями). Обычно это позволяет найти ответ для более широкого класса задач.

Буду рад комментариям на эту тему.