algorithm - 使用动态规划的问题 k-subvector

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 有点棘手。我们可以使用哈希表存储窗口内的每个元素在那里出现了多少次。

因此，允许正确增加的条件看起来像

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

每次 left 或 right 增加时，我们都需要更新散列(减少或增加给定元素的出现次数)。

我很确定，这里的任何 DP 解决方案都会更长更复杂。