Динамично програмиране в JavaScript

Динамичното програмиране е техника, използвана в компютърните науки за ефективно решаване на сложни проблеми чрез разделянето им на по-малки подпроблеми и съхраняване на решенията в таблица или матрица. В това ръководство ще изследваме задълбочено динамичното програмиране, обсъждайки неговите принципи, общи техники и приложения в JavaScript.

Принципи на динамичното програмиране

Динамичното програмиране се основава на два принципа: оптимална подструктура и припокриващи се подпроблеми.

Оптимална подструктура означава, че може да се намери оптимално решение на по-голям проблем чрез комбиниране на оптимални решения на по-малки подпроблеми.

Припокриващи се подпроблеми се отнасят до факта, че едни и същи подпроблеми се срещат многократно в даден проблем.

Динамичното програмиране се възползва от тези два принципа за решаване на проблеми по ефективен начин, като разделя проблема на по-малки подпроблеми, решава ги и съхранява техните решения в таблица или матрица. След това решенията се комбинират, за да се реши по-големият проблем.

Техники за динамично програмиране

Има две основни техники, използвани в динамичното програмиране: отгоре надолу (мемоизация) и отдолу нагоре (табулиране).

Динамичното програмиране отгоре надолу, известно още като мемоизация, включва разделяне на проблем на по-малки подпроблеми и съхраняване на решенията на тези подпроблеми в таблица или матрица. Когато решавате по-големия проблем, решенията на подпроблемите се търсят в таблицата или матрицата, за да се избегне излишно изчисление.

Динамичното програмиране отдолу нагоре, известно още като таблично излагане, включва първо решаване на подпроблемите и съхраняване на техните решения в таблица или матрица. След това решенията на по-големия проблем се изчисляват с помощта на решенията на подпроблемите.

Често срещани проблеми с динамичното програмиране

Поредица на Фибоначи

Последователността на Фибоначи е поредица от числа, където всяко число е сбор от двете предходни числа. Последователността започва с 0 и 1, като всяко следващо число е сбор от двете предходни числа.

При динамичното програмиране можем ефективно да изчислим n-то число на Фибоначи, като разделим проблема на по-малки подпроблеми и съхраним техните решения в таблица или матрица.

Ето пример за изчисляване на n-то число на Фибоначи с помощта на динамично програмиране отдолу нагоре в JavaScript:

function fibonacci(n) {
  if (n < 2) {
    return n;
  }

  let table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}

В този пример започваме с проверка дали n е по-малко от 2. Ако е, просто връщаме n. Ако не, създаваме таблица с първите две числа на Фибоначи (0 и 1). След това използваме цикъл, за да изчислим следващите n — 1 числа на Фибоначи и да ги съхраним в таблицата. Накрая връщаме n-то число на Фибоначи, което е последният елемент в таблицата.

2. Най-дългата нарастваща подпоследователност

Проблемът с най-дългата нарастваща подпоследователност включва намирането на най-дългата подпоследователност от дадена последователност, която е строго нарастваща.

При динамичното програмиране можем да разрешим този проблем ефективно, като го разделим на по-малки подпроблеми и съхраним техните решения в таблица или матрица.

Ето пример за изчисляване на най-дългата нарастваща подпоследователност с помощта на динамично програмиране отдолу нагоре в JavaScript:

function longestIncreasingSubsequence(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

В този пример започваме с инициализиране на масив dp с всички елементи, зададени на 1, тъй като всеки елемент в последователността е подпоследователност с дължина 1. След това използваме вложен цикъл, за да сравним всяка двойка елементи в последователността. Ако елементът с индекс j е по-малък от елемента с индекс i, актуализираме стойността на dp[i], за да бъде максималната от текущата му стойност и dp[j] + 1. Това означава, че обмисляме разширяване на подпоследователността, която завършва при индекс j с елемента при индекс i и вземете максималната дължина на всички такива разширения на подпоследователност. Накрая връщаме максималната стойност в dp масива, която е дължината на най-дългата нарастваща подпоследователност.

Алгоритми за динамично програмиране

Запаметяване

Мемоизацията е техника за динамично програмиране отгоре надолу, която включва разбиване на проблем на по-малки подпроблеми и съхраняване на решенията на тези подпроблеми в таблица или матрица. Когато решавате по-големия проблем, решенията на подпроблемите се търсят в таблицата или матрицата, за да се избегне излишно изчисление.

Ето пример за изчисляване на n-то число на Фибоначи с помощта на мемоизация в JavaScript:

function fibonacci(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }

  if (n < 2) {
    return n;
  }

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

В този пример започваме с проверка дали n вече е в таблицата за запомняне. Ако е, връщаме стойността му. Ако не, ние изчисляваме n-то число на Фибоначи рекурсивно чрез рекурсивно изчисляване на (n-1)-то и (n-2)-то число на Фибоначи и съхраняваме тяхната сума в таблицата за запаметяване. Това гарантира, че изчисляваме всяко число на Фибоначи само веднъж и следващите извиквания за същото число ще бъдат извлечени от таблицата за запаметяване.

2. Табулирането

Табулирането е техника за динамично програмиране отдолу нагоре, която включва първо решаване на подпроблемите и съхраняване на техните решения в таблица или матрица. След това решенията на по-големия проблем се изчисляват с помощта на решенията на подпроблемите.

Ето пример за изчисляване на n-то число на Фибоначи с помощта на таблична таблица в JavaScript:

function fibonacci(n) {
  if (n < 2) {
    return n;
  }

  let table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}

Заключение

Динамичното програмиране е мощна техника, използвана за ефективно решаване на сложни проблеми, като ги разделя на по-малки подпроблеми и съхранява техните решения в таблица или матрица. В JavaScript динамичното програмиране може да се реализира с помощта на мемоизация или табулиране, в зависимост от проблема. Някои често срещани проблеми, които могат да бъдат решени с помощта на динамично програмиране, включват последователността на Фибоначи и най-дългата нарастваща подпоследователност. Като разберете принципите и техниките на динамичното програмиране, вие можете да решавате ефикасно и ефективно широк кръг от проблеми.

Динамично програмиране в JavaScript

Подобни въпроси