使用动态规划解决k-子向量问题

Question

给定一个由 n 个整数组成的向量 V 和一个整数 k，k <= n，您需要一个最大长度的子向量（向量 的连续元素的序列），最多包含 k 个不同元素。

我用来解决问题的技术是动态规划。 该算法的复杂度必须是O(n*k)。

主要问题是如何计算向量的不同元素。你会怎样解决呢？

递归方程怎么写？

感谢您！！！。

Answer 1

我不知道为什么你会坚持O(n*k)，这可以通过“滑动窗口”方法在O(n)中解决。

1. 维护当前的“窗口”[left..right]
2. 在每一步中，如果我们可以将 right 加 1（不违反“最多 k 个离散元素”要求），则执行否则
3. ，将 left 增加 1
4. 检查当前窗口是否是最长的，然后返回#2

检查是否可以在 #2 中增加 right 有点棘手。我们可以使用哈希表来存储窗口内每个元素出现的次数。

因此，允许 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 ;-)

我还可以告诉你一个在 O(n*b) 中对 V 进行排序的算法，其中 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
开始索引 = 0
结束索引 = n-1
currentBit = 整数的位数 (=: b)​​-1。

这甚至根据要求使用动态编程。

您可以很容易地确定，这是 O(n*b) 时间，递归深度为 b。