У динамического программирования репутация метода, который вы изучаете в университете, а затем вспоминаете только на собеседованиях. Но на самом деле метод применим во многих ситуациях. По сути, это техника эффективного решения задач, которые можно разбить на множество сильно повторяющихся подзадач.
В статье я покажу интересное реальное применение динамического программирования — задача вырезания швов (seam carving). Задача и методика подробно описаны в работе Авидана и Шамира «Вырезание швов для изменения размеров изображения с учётом контента» (статья в свободном доступе).
Эта одна из серии статей по динамическому программированию. Если хотите освежить в памяти методы, см. иллюстрированное введение в динамическое программирование.
Читать полностью »