Помимо того, что динамическое программирование является приемлемым способом получить прилив серотонина, это еще один способ сократить временную сложность.

Так что же такое динамическое программирование? Динамическое программирование - это практика, при которой вы разбиваете проблему, зависящую от более мелких проблем, а затем оптимизируете временную сложность этих проблем, чтобы улучшить временную сложность общей проблемы.

Сложность времени относится к количеству времени, которое необходимо программе для выполнения. Существует ряд терминов для обозначения различной сложности времени. Лучшим и самым коротким является линейное время, при котором на каждый вход приходится одна итерация. Чтобы было ясно, если у вас есть массив (список), и вы хотите перебрать каждый из них, чтобы консоль регистрировать их, это будет линейное время.

const nums = [1,2,3,4];
    nums.map(num => {
       console.log(num);
    });

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

//fibonacci sequence
    const fibonacci = [1,1,2,3,5,8,13,21,34,55,89]; //goes on forever

Общая формула для определения временной сложности при включении динамического программирования - это количество уникальных вычислений * время, затраченное на одно вычисление.

Для последовательности Фибоначчи решение методом грубой силы для нахождения числа на n-м месте в последовательности Фибоначчи выглядит примерно так:

const fibonacci = (n) => {
    if (n <= 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
};

Эта реализация поиска n-го члена в последовательности Фибоначчи выполняется с помощью рекурсии и имеет временную сложность 2 ^ n или экспоненциальное время.

Это можно сократить с помощью динамического программирования, и тогда вы, надеюсь, исправите серотонин.

Реализация:

Мемоизация

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

Итак, вы заметите, что в примере Фибоначчи мы повторяем те же вычисления, когда вызываем его со значением больше 3. Вот пример вызова функции с числом 7:

На графике выше правую часть графика можно рассматривать как часть левой. Значит, мы пересчитываем эту часть заново. Конечно, это не займет много времени, так как наш компьютер сможет с этим справиться, но когда число становится слишком большим, программа резко замедляется. Итак, как нам включить динамическое программирование в предыдущее решение?

Поскольку мы хотим сделать нашу программу как можно более быстрой, у нас должен быть способ сохранять и извлекать значения из этого хранилища как можно быстрее. В javascript мы бы использовали объект, поскольку они хранят с помощью пар ключ-значение, доступ к которым можно получить за линейное время с помощью ключа.

const fibonacci = (n, memo = {}) => {
    if(memo[n]){
        return memo[n];
    }
    if (n <= 2) {
        return 1;
    }
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2,memo);
};

В приведенном выше коде есть новый параметр под названием memo, сокращение от memoization. Этот объект будет функционировать как хранилище, к которому можно будет получить доступ в линейное время, используя n-й член в качестве ключа. Это приводит к сокращению вычислений, поскольку нам не нужно пересчитывать какие-либо значения, которые уже были рассчитаны и сохранены в памятке.

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

Табулирование

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

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

Поскольку мы знаем, как последовательность Фибоначчи начинается как 0,1, мы можем сделать из этого массив и последовательно вставлять в него новые значения и извлекать n-е значение, используя индекс. Кроме того, для тех из вас, кому интересно, я начинаю массив с 0, потому что последовательность Фибоначчи технически начинается с нуля, но нет необходимости включать в сумму, поскольку все, что плюс ноль, по-прежнему равно нулю.

В любом случае, вот код для нашей таблицы:

const fibonacci = (n) => {
    const tab = [0,1];
    for (let i = 2; i <= n; i++) {
        tab[i] = tab[i - 1] + tab[i - 2];
    }
    return tab[n];
};

Теперь вы можете заметить, что в этом методе нет рекурсии. Это означает, что мы никогда не достигнем максимальной глубины стека вызовов, поскольку мы никогда не вызовем одну и ту же функцию снова.

Заключение

Итак, чтобы очистить всю эту информацию, динамическое программирование - это просто практика, которая помогает сократить временную сложность / ускорить работу вашей программы. Хорошо, надеюсь, вы получили дозу серотонина на день.