降低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算法，我們使用了多種方便的子算法，如排序，樹（即使它不是算法），...

如果你想減少時間複雜度，體現了這一算法更快速。

如果您使用排序，請使用快速排序或堆排序而不是選擇/冒泡排序。

如果您想獲取最小/最大值，請使用堆或優先級隊列。

如果無法制作更快的遞推公式，那麼使用更快的子算法可以縮短時間。