Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач «меньшего размера» и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размеров — от меньших к большим. Преимущество динамического программирования заключается в том, что раз уж какая-то подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново [Шень 95, п. 8.1; Ахо 79, п. 2.8].
В том случае, когда исходная задача определяется одним параметром N, имеющим смысл «размера задачи», идея динамического программирования сродни идее метода математической индукции. А именно, предположим, что мы уже знаем ответ Fk на задачу размера k для всех k, меньших N, и хотим вычислить ответ для k, равного N. Если нам удастся выразить этот ответ через уже известные, то тем самым получен алгоритм решения задачи для произвольного N: отталкиваясь от нескольких начальных значений F0, F1, …, Fs, вычисляем в цикле числа Fs+1, Fs+2 и т.д. до искомого значения FN.
Решение многих задачах, представленных в этой главе, требует реализации арифметики многократной точности, называемой иначе . Алгоритмы и структуры данных, необходимые для этого, описаны в [Кнут 78, п. 4.3]. Модуль, реализующий операции с длинными числами, может быть получен на http://antosha.com/onzi/modules.html.
| Задача | Программа | Тесты |
|---|---|---|
| 1.1. Последовательности из 0 и 1 |  |
 |
| 1.2. Восстановление скобок | |
|
| 1.3. Уравнение с пропущенными цифрами | |
|
| 1.4. Ход конем | |
|
| 1.5. Дырокол | |
|
| 1.6. Сжатие текста | |
|
| 1.7. Пустоты в кубе | |
|
| 1.8. Шаблоны с ? и * | |
|
| 1.9. Ну и имечко! |  |
|
| 1.10. Жадный калькулятор | |
|
| 1.11. Взлом сети | |
|
| 1.12. Параллельные вычисления | |
|
| 1.13. Длинный путь в графе | |
|
| 1.14. Навстречу друг другу | |
|