Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач "меньшего размера" и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размеров - от меньших к большим. Преимущество динамического программирования заключается в том, что раз уж какая-то подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново [Шень 95, п. 8.1; Axo 79, п. 2.8]

В том случае, когда исходная задача определяется одним параметром N, имеющим смысл "размера задачи", идея динамического программирования сродни идее метода математической индукции. А именно, предположим, что мы уже знаем ответ F_k на задачу размера k для всех k меньших N, и хотим вычислить ответ для k, равного N. Если нам удастся выразить этот ответ через уже известные, то тем самым получен алгоритм решения задачи для произвольного N: отталкиваясь от нескольких начальных значений F₀, F₁,..., F_S, вычисляем в цикле числа F_S-1, F_S-2 и т.д. до искомого значения F_N

Решение многих задач, представленных в этой главе, требует реализации арифметики многократной точности, называемой иначе длинной арифметикой. Алгоритмы и структуры данных, необходимые для этого, описаны в [Кнут 78, п.4.3]. Модуль, реализующий операции с длинными числами, можно получить здесь