Принцип динамического программирования при построении алгоритмов заключается в разбиении сложной задачи на более простые подзадачи. 14

При этом каждая подзадача решается только один раз, а её результат сохраняется для дальнейшего использования. 2 Это позволяет исключить лишние операции и заметно ускорить выполнение алгоритмов. 2

Метод основывается на двух ключевых принципах: 1

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