algorithm - 降低 DP 算法时间复杂度的一般技巧

Question

因此，当我在处理编程竞赛(ACM ICPC 等)中的一些练习题时，人们通常可以采用 O(N^2) 解决方案，甚至更糟，并使用堆(C++ 中的 priority_queue)或双端队列以降低复杂性。 (作为某种优化，在注意到模式中的“某些东西”之后)

例如在“滑动窗口最大值”问题中，差不多就是:

For each window of size K in an array of size N, compute the maximum.

有一个简单的 O(NK) 算法，一个相当简单的 O(nlogn) 解决方案(即使我可以看到它，使用堆)和一个 O(N) 解决方案，使用双端队列。

这些原则似乎是“丢弃”无用值的原则，或者查询区域以查找属性(最大值、累积和、最小值等)。

例如，将一些 O(N^2) 算法转换为 O(NlogN)，有时您可以使用 priority_queue 并不断弹出值，直到在某个窗口内获得一个值，而不是循环遍历所有先前的 N 个元素以找到最大值。

谁有好的建议？ (除了做更多的问题......我正在尝试这样做)

Answer 1

DP算法的基础是 split 问题。

为了降低时间复杂度，让我们以不同的方式拆分问题。

为了体现DP算法，我们使用了许多简单的子算法，例如排序，树(即使不是算法)，......

如果要降低时间复杂度，请更快地体现该算法。

如果您正在使用排序，请使用快速排序或堆排序而不是选择/冒泡排序。

如果你想得到最小值/最大值，使用堆或优先队列。

如果你不能做出更快速的递归公式，那么使用更快速的子算法来减少时间。