Динамическое программирование

Динамическое программирование (ДП) — это точный метод оптимизации, введенный Ричардом Беллманом в 1957 году для решения многоэтапных задач принятия решений. Он разлагает сложную задачу на более простые, перекрывающиеся подзадачи, решает каждую подзадачу один раз и сохраняет результаты, чтобы избежать избыточных вычислений. Основанное на Принципе оптимальности, ДП гарантирует глобально оптимальные решения, когда задача обладает перекрывающимися подзадачами и оптимальной подструктурой.