本地搜索

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）中解决。