В этой статье рассматриваются сходства и различия двух подходов к решению алгоритмических задач: динамического программирования (dynamic programing) и принципа «разделяй и властвуй» (divide and conquer). Сравнение будем производить на примере, соответственно, двух алгоритмов: бинарного поиска (как быстро найти число в отсортированном массиве) и расстояния Левенштейна (как преобразовать одну строку в другую с минимальным количеством операций).
Хочу сразу заметить, что данное сравнение и объяснение не претендует на исключительную правильность. И возможно даже некоторые преподаватели в университетах захотели бы меня отчислить :) Эта статья является всего-лишь моей персональной попыткой разложить себе же все по полочками и понять что такое динамическое программирование и каким образом в нем участвует принцип «divide and conquer».
Итак, приступим…
