Источник: Nuances of Programming Предыдущая часть: “Структуры данных: подход «разделяй и властвуй»” Подход динамического программирования схож с подходом «разделяй и властвуй»: тоже разбивает задачи на как можно более мелкие подзадачи. Отличие в том, что здесь подзадачи решаются не независимо. Результаты этих более мелких подзадач запоминаются и используются для аналогичных или перекрывающихся подзадач. Динамическое программирование применяется там, где есть задачи, которые можно разделить на похожие подзадачи, а их результаты использовать повторно...

Разделяй и властвуй (англ. divide and conquer) — это принцип разработки алгоритмов, при котором задачу разбивают на две или более подзадачи того же типа, но меньшего размера. Их комбинируют так, чтобы в результате получить ответ к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными — базовыми. Стратегия «разделяй и властвуй» работает так: 1 Шаг. Определяем простейший случай — базовый. 2 Шаг. Находим способ свести задачу к базовому случаю. Рассмотрим пример: Имеется массив чисел...