Скажем, у нас есть массив A, который содержит N целых чисел. Проблема состоит в том, что мы хотим минимизировать стоимость некоторой увеличивающейся подпоследовательности (не обязательно строго возрастающей), начиная с позиции 1 и заканчивая в позиции N. Общая стоимость подпоследовательности - это общая стоимость перехода между элементами в подпоследовательности. При построении подпоследовательности стоимость перехода из положения j в положение i, где i> = j, может быть найдена в матрице COST [i] [j]. Гарантируется, что существует некоторая возрастающая подпоследовательность, в которой мы начинаем с позиции 1 и достигаем позиции N. Значения в массиве могут быть очень большими.
Например:
N = 5
A = [0,3,2,3,3]
Стоимость =
[[0, INF, INF, INF, INF],
[ 3,0, INF, INF, INF],
[3, INF, 0, INF, INF],
[5,2,2,0, INF],
[6,0,3,1,0]]
Подпоследовательность с наименьшей стоимостью увеличивается (A [1], A [2], A [5]) или (0,3, 3).
Стоимость составляет СТОИМОСТЬ [2] [1] + СТОИМОСТЬ [5] [2] = 3 + 0 = 3.
До сих пор я был в состоянии изменить традиционный O (n ^ 2) dp решение, инициализируя dp [i] бесконечностью и dp [1] равным 0, а затем повторяя все предыдущие значения для расширения подпоследовательности. Перебирая предыдущие значения, я просто поддерживаю минимальную стоимость.
Теперь я хочу улучшить это решение и сделать его o (nlogn). Я знаю, что обычную проблему LIS можно решить с помощью массивов и двоичного поиска, но я не смог изменить такой подход, чтобы соответствовать этой проблеме.