algorithm - CFG算法中的局部搜索

有没有一种算法可以在多项式时间内解决以下问题:

我们在 bitset 中连接位:

0 只能连接到 1

每个位只能连接一次

连接不能相交

给定位集的最大连接数是多少？

最佳答案

我们可以在这里使用动态规划。

状态是 (l, r) - 给定字符串的 [l, r] 子字符串。

状态值是子串内匹配符号的最大数量。

基本情况是微不足道的:对于所有短于 2 的子串，答案为 0。

对于所有更长的子串，我们可以做两件事:

不匹配第一个符号。

将其与某事物匹配并独立解决两个较小的子问题(它们是独立的，因为不允许交叉)。

就是这样。时间复杂度是 O(n^3)(每个状态都有 O(n^2) 状态和 O(n) 转换)。这是一个伪代码(为简洁起见，省略了内存):

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

关于algorithm - CFG算法中的局部搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30277809/