Динамическое программирование — способ решения задач путём разбиения их на подзадачи, которые, в свою очередь, используются для нахождения ответа исходной задачи. Сейчас мы разберём одну классическую задачу динамического программирования.

Числа трибоначчи
Числа трибоначчи — это числовой ряд, начинающийся с трёх чисел 0, 0, 1, где каждое последующее число вычисляется как сумма трёх чисел перед ним:

Рассмотрим следующую задачу: дан массив чисел с порядковыми номерами чисел трибоначчи, например: [73, 10, 4, 15, 20, 7], числа в массиве не превышают 100, требуется вернуть массив, содержащий числа трибоначчи под указанными номерами: [73-е число трибоначчи, 10-е число трибоначчи, и так далее].

Если вы какое-то время работаете с языками программирования, то наверняка решали задачи нахождения факториала или степени числа через рекурсию. Попробуем применить такую же идею здесь:

const tribonacciNumber = (n) => {
// обрабатываем граничные условия, их три,
// т.к. рекурсия будет идти на 3 числа внутрь
if (n === 1 || n === 2) return 0;
if (n === 3) return 1;

return tribonacciNumber(n - 1) +
tribonacciNumber(n - 2) +
tribonacciNumber(n - 3);
}
Запускаем функцию с вычислением времени:

console.time();
console.log(tribonacciNumber(36));
console.timeEnd(); // 6337 ms

console.time();
console.log(tribonacciNumber(37));
console.timeEnd(); // 11361 ms

console.time();
console.log(tribonacciNumber(40));
console.timeEnd(); // 71015 ms

console.time();
console.log(tribonacciNumber(41));
console.timeEnd(); // 135573 ms
41-е число вычисляется 135 секунд. Кажется, что быстрее вручную посчитать числа, подставить в массив все 100 значений (ограничение задачи) и просто вернуть число на нужной позиции. В чём же проблема, как так получилось, что простой алгоритм работает так долго? Можно заметить, что следующее число вычисляется в 2 раза дольше, чем предыдущее. Давайте посмотрим на рекурсивное дерево вызовов:

Можно заметить, что при вычислении через рекурсию многие числа будут считаться по несколько раз, например, число 37 будет посчитано 6 раз. В замерах времени выше мы видели, что вычисление этого занимает 11 секунд, т.е. займёт половину времени от вычислений числа 41 — 66 секунд из 135.

Напрашивается решение проблемы — запоминать вычисленные значения и при необходимости просто их использовать. Давайте посмотрим, что получается в таком случае:

// хранит вычисленные числа трибонначи,
// в виде "число трибонначи": "значение числа"
const tribonacciNumbersCache = {};

const tribonacciNumber = (n) => {
if (n === 1 || n === 2) return 0;
if (n === 3) return 1;

// проверяем, было ли вычислено значение числа n
// если да, то просто возвращаем это значение
if (n in tribonacciNumbersCache) {
return tribonacciNumbersCache[n];
}

// вычисляем значения
const nTribonacciNumber = tribonacciNumber(n - 1) +
tribonacciNumber(n - 2) +
tribonacciNumber(n - 3);

// сохраняем вычисленное значение, для переиспользования
tribonacciNumbersCache[n] = nTribonacciNumber;

return nTribonacciNumber;
}
Пробуем выполнить новую функция с теми же входными данными:

console.time();
console.log(tribonacciNumber(36));
console.timeEnd(); // 0.26 ms

console.time();
console.log(tribonacciNumber(37));
console.timeEnd(); // 0.11 ms

console.time();
console.log(tribonacciNumber(40));
console.timeEnd(); // 0.10 ms

console.time();
console.log(tribonacciNumber(41));
console.timeEnd(); // 0.09 ms
Во-первых, мы видим, что выполнение теперь занимает доли миллисекунд. Во-вторых, замечаем понижение времени при каждом новом вызове. Это связано с оптимизациями компилятора JavaScript после определенного количества вызова кода. После пары вызовов время уменьшается на 0.1 миллисекунды (для моего компьютера), следовательно, 100 вычислений, которые нам требуются для исходной задачи, пройдут за 0.01 секунду.

Мы уже применили идеи динамического программирования — сохранили результат вычисления подзадачи для получения результата следующей задачи. Осталось вызвать это в цикле для исходного массива и получить ответ. Но что делать, если в вычисления закрадётся ошибка? Код с рекурсией отлаживать довольно сложно.

Давайте немного упростим решение за счёт идеи предварительного вычисления всех возможных вариантов. Это займёт очень мало времени, т.к. по условию задачи максимальное число — 100, и за счет идеи отказа от рекурсии. Будем считать так, как бы мы считали эти числа на листике, руками:

const tribonacciNumbersCache = [0, 0, 1];

// i < 100, не включая 100, т.к. 100-е число будет находиться в 99 позиции
for (let i = 3; i < 100; i++) {
// используем предыдущие 3 значение из массива, никакой рекурсии
tribonacciNumbersCache.push(tribonacciNumbersCache[i - 1] +
tribonacciNumbersCache[i - 2] +
tribonacciNumbersCache[i - 3])
}
Поскольку идем, увеличивая число i, и у нас изначально добавлено в массив tribonacciNumbersCache три значения, то получение элементов i - 1, i - 2 и i - 3 отработает без ошибок.

В 0 позиций массива tribonacciNumbersCache — первое число трибонначи, главное не забыть вычитать единицу при получении значения.

Напишем решение исходной задачи — по массиву номеров получить массив с числами трибонначи:

const tribonacciNumbersCache = [0, 0, 1];

for (let i = 3; i < 100; i++) {
tribonacciNumbersCache.push(tribonacciNumbersCache[i - 1] +
tribonacciNumbersCache[i - 2] +
tribonacciNumbersCache[i - 3])
}

const tribonacciNumbers = [73, 10, 4, 15, 20, 7];
// массив для сохранения самих чисел трибонначи
const tribonacciNumbersValue = [];

for (const number of tribonacciNumbers) {
// просто получаем значения из кеша, не делая никаких вычислений
tribonacciNumbersValue.push(tribonacciNumbersCache[number - 1])
}

console.log(tribonacciNumbersValue);
В консоль будет выведено [2073693258389777400, 44, 1, 927, 19513, 7]. Задача решена.

Основные идеи

Мы использовали несколько подходов, типичных для динамического программирования:

Определили, как из известных данных маленьких подзадач будет вычисляться следующая подзадача, т.е. с числами трибонначи из трёх значений будет вычисляться следующее значение. Это соотношение называется рекурсивным.
Нашли исходные данные, чтобы можно было запустить наше вычисление.
Определили, откуда брать ответ — вычитали единицу при обращении к элементу массива с посчитанными значениями.

Больше подобных задач с разбором на сайтах: статья 1, статья 2