Динамическое программирование в 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

Похожие вопросы