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

Что нужно, чтобы решить задачу динамически, помимо ее исходных данных? Всего три вещи:

  • Начальные значения, которые мы зададим перед началом динамики.
  • Формула пересчета, от предыдущих значений. Универсального рецепта тут нет и к каждой задаче требуется свой подход.
  • Нужно понять, где в нашем массиве будет лежать ответ.

Давайте разберем этот принцип на ряде Фибоначчи:

\[F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1}\]
  • Начальные значения: \(F_0 = 0, F_1 = 1\)
  • Формула пересчета: \(F_n = F_{n-2} + F_{n-1}\)
  • Для \(N\)-го числа ответ будет в \(N\) ячейке

Задача о рюкзаке:

Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью \(S\), если есть \(N\) золотых слитков с заданными весами.

Однозначно мы можем достичь веса в 0 кг.

Теперь мы будем утверждать, что если мы достигли какое-то множество весов \(A=\{0, x_1, x_2, … x_k)\) и у нас есть новый слиток весом \(x_t\), то новое множество весов, которые мы сможем достичь будет \(A = \{0, 0+x_t, x_1, x_1+x_t, x_2+x_t … x_k, x_k+x_t)\), если какой либо из новых весов больше \(S\), мы их отбрасываем.

Таким образом мы пройдемся по всем весам, ответ будет хранится в последней ячейке. Реализовать такое можно на \(std::bitset\) \(c++\) логическими операциями.

d |= d << arr[i];

Наибольшая общая подпоследовательность (НОП):

Пусть имеются последовательности \(X=⟨ x_1,x_2,…,x_m⟩\) и \(Y=⟨ y_1,y_2,…,y_n⟩\). Необходимо найти \(LCS(X,Y)\) (Наибольшую общую подпоследовательность).

Пусть имеются последовательности \(X=⟨ x_1, x_2, … , x_m⟩\) и \(Y=⟨ y_1 , y_2, … , y_n⟩\), а \(Z=⟨ z_1, z_2, … ,z_k⟩\) — их \(LCS\).

  1. Если \(x_m=y_n\), то \(z_k=x_m=y_n\) и \(z_(k-1)\) — \(LCS(X_(m-1),Y_(n-1))\)
  2. Если \(x_m≠y_n\), то из \(z_k≠x_m\) следует, что \(Z\) — \(LCS(X_(m-1),Y)\)
  3. Если \(x_m≠y_n\), то из \(z_k≠y_n\) следует, что \(Z\) — \(LCS(X,Y_(n-1))\)

Обозначим как \(lcs[i][j]\) LCS префиксов данных последовательностей, заканчивающихся в элементах с номерами \(i\) и \(j\) соответственно. Получается следующее рекуррентное соотношение:

\[lcs[i][j] = \begin(cases) 0, если i = 0 или j = 0, lcs[i - 1][j - 1] + 1, если x[i] = y[j], max(lcs[i - 1][j], lcs[i][j - 1]), если x[i] ≠ y[j]. \end(cases)\]

Очевидно, что сложность алгоритма составит \(O(m*n)\), где \(m\) и \(n\) — длины последовательностей.

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