本地搜索

Question

有沒有可以解決在多項式時間如下問題的算法：

我們連接位的bitset：

• 0只能連接到1
• 各位只能連接一次
• 的連接不能相交

什麼是最大的Amoun給定bitset的連接？

Answer 1

我們可以在這裏使用動態編程。

1. 的狀態是(l, r) - 一個[l, r]子給定的字符串。

2. 狀態的值是子字符串中匹配符號的最大數量。

3. 基本情況很簡單：所有的子短於2，答案0

4. 對於所有的長串，我們可以做兩件事情：

   • 不匹配第一符號到任何東西。

   • 將其與某事匹配並獨立解決兩個較小的子問題（它們是獨立的，因爲不允許交集）。

就是這樣。時間複雜度爲O(n^3)（有O(n^2)個狀態和O(n)從它們中的每個轉換）。下面是一個僞代碼（爲了簡潔省略memoization的）：

def calc(l, r) 
    if l >= r 
     return 0 
    res = calc(l + 1, r) 
    for k = l + 1 to r 
     if match(s[l], s[k]) // match checks that two characters match 
      res = max(res, 1 + calc(l + 1, k - 1) + calc(k + 1, r)) 
    return res 

Answer 2

實際上，在0和1的一個給定序列的連接的最大數量在這兩個值中的最小值 - 在順序和數量的0的數1秒的順序。

當無法連接少數中的所有位時，就沒有這種情況。所以這個問題可以在O（n）中解決。