將一行對象拆分爲

Question

我無法快速解決此問題。我有一個迭代的O(M*N^2)動態編程解決方案，但它似乎太慢了。

這裏的問題：

鑑於N人物（無論是「A」或「B」）在一條線上，我們嘗試把多達M非重疊雨傘上空字符，這樣，在所有的遮陽傘覆蓋所有人物。有兩種類型的雨傘：「傘」和「傘」。放置在範圍[i,j]上的「a」傘的分數等於該範圍中「a」字符的數量。 「b」傘以相似的方式運行。當從左向右讀，雨傘必須型交替（這是顯而易見的，因爲可以只結合相同類型的相鄰雨傘。）

例如，如果N=8和M=2和字符是abaabbab則最優解將從[0,3]和[4,7]的「b」傘放置一把「a」傘。

我的解決辦法是DP，其中maxscore(index, used, type)是覆蓋0...index與used傘，隨着最後傘是type類型的最大比分。有N*M*2狀態和O(N)轉換（考慮前一傘的所有可能的結束），這使得它O(M*N^2)和運行速度太慢。有更快的DP算法嗎？

Answer 1

我懷疑你當前的遞歸是根據maxscore的值計算maxscore，它是在以前所有位置上的相反類型。這給出了每個狀態的O（N）計算。

但是，您可以通過簡單考慮是否啓動新的保護傘或繼續前一個保護傘並選擇這兩個選項中的最佳選項，將其降至每個狀態的O（1）計算。

如果我們啓動一個新的保護傘，那麼得分爲maxscore(index-1,used-1,1-type)加1，如果當前字符匹配類型。

如果我們繼續前一個，那麼得分爲maxscore(index-1,used,type)加1，如果當前字符匹配類型。