Задача k-подвектора с использованием динамического программирования

Question

Для вектора V из n целых чисел и целого числа k, k <= n, требуется субвектор (последовательность последовательных элементов вектора) максимальной длины, содержащий не более k отдельных элементов.Техника, которую я использую для решения проблемы, - это динамическое программирование.Сложность этого алгоритма должна быть O (n * k). </p>

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

Как написать УРАВНЕНИЕ РЕКУРРЕНЦИИ?

Спасибо вам !!!.

Answer 1

Я не знаю, почему вы настаиваете на O(n*k), это можно решить за O(n) с подходом «скользящего окна».

1. Поддерживать текущее «окно» [left..right]
2. На каждом шаге, если мы можем увеличить right на 1 (не нарушая требование «не более k элементов»), сделайте это
3. В противном случае увеличить left на 1
4. Проверьте, является ли текущее окно самым длинным и вернитесь к # 2

Проверить, можем ли мы увеличить right в # 2, немного сложно. Мы можем использовать хеш-таблицу для хранения каждого элемента внутри окна, сколько раз это происходило там.

Итак, условие, позволяющее увеличить right, будет выглядеть

hash.size < k || hash.contains(V[right + 1])

И каждый раз, когда left или right увеличивается, нам нужно обновлять хеш (уменьшать или увеличивать количество вхождений данного элемента).

Я уверен, что любое решение DP здесь будет длиннее и сложнее.

Answer 2

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

Если вы разрешите использовать хеширование, вы можете сделать следующее

init Hashtable h
distinct_count := 0
for each element v of the vector V
    if h does not contain v (O(1) time in average)
        insert v into h (O(1) time in average)
        distinct_count := distinct_count + 1
return distinct_count

Это среднее время O (n).

Если здесь нет решения O (n log n) - на этот раз наихудший случай

sort V (O(n log n) comparisons)
Then it should be easy to determine the number of different elements in O(n) time ;-)

Я также мог бы рассказать вам алгоритм сортировки V по O (n * b), где bэто число битов целых чисел - если это поможет вам.

Вот алгоритм:

sort(vector, begin_index, end_index, currentBit)
    reorder the vector[begin_index to end_index] so that the elements that have a 1 at bit currentBit are after those that have a 0 there (O(end_index-begin_index) time)
    Let c be the count of elements that have a 0 at bit currentBit (O(end_index-begin_index) time; can be got from the step before)
    if (currentBit is not 0)
        call sort(vector, begin_index, begin_index+c)
        call sort(vector, begin_index+c+1, end_index)

Вызовите его с вектором = V begin_index = 0 end_index = n-1currentBit = число битов целых чисел (=: b) ​​-1.

Это даже использует динамическое программирование в соответствии с запросом.

Поскольку вы можете очень легко определить, что это O (n * b) времяс глубиной рекурсии b.