Динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения.. Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи»
Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.
В типичном случае динамическое программирование применяется кзадачам оптимизации
У такой задачи может быть много возможных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). В общем случае, оптимум может достигаться для нескольких разных решений.
Построение алгоритма, основанного на динамическом программировании.
Надо:
1) описать строение оптимальных решений,
2) выписать рекуррентное соотношение, связывающее оптимальные значения параметра для подзадач,
3) двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач,
4) пользуясь полученной информацией, построить оптимальное решение.