Специфика решения задач динамического программирования заключается в следующем:

1. Разделение основной проблемы на более мелкие, независимые подзадачи. 4 Каждую подзадачу решают независимо и сохраняют решение в таблице или массиве. 4
2. Использование сохранённых решений для создания решения основной проблемы. 4 При этом одна и та же подзадача не решается дважды, что сокращает время вычислений. 14

Кроме исходных данных, для динамического решения задачи требуется: 1

• Таблица для сохранения итогов промежуточных вычислений. 1 При завершении работы среди них будет выбран окончательный результат. 1
• Набор правил, по которым заносятся данные в пустые ячейки таблицы, исходя из значений в уже заполненных ячейках. 1 Для каждой задачи правила составляются индивидуально. 1
• Правило, по которому из заполненной таблицы получается готовый ответ. 1

Динамическое программирование требует глубокого понимания структуры задачи и умения выявлять повторяющиеся подзадачи. 3