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

Question

因此，当我在编程比赛（ACM ICPC等）中遇到一些练习问题时，人们通常会花费O（N^2）个解决方案，甚至更糟糕，而且使用堆（C++中的priority_queue）或deque来降低复杂性。在“滑动窗口最大”的问题

例如，这是相当多的（如某种优化，注意到在模式“东西”后）：

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算法是分裂的问题。

为了减少时间复杂度，让我们以不同的方式分解问题。

实施方案DP算法，我们使用了多种方便的子算法，如排序，树（即使它不是算法），...

如果你想减少时间复杂度，体现了这一算法更快速。

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

如果您想获取最小/最大值，请使用堆或优先级队列。

如果无法制作更快的递推公式，那么使用更快的子算法可以缩短时间。