algorithm - 分割一串括号

Question

有人能帮我解决这个问题吗？我将把问题打出来，然后给出我的一些想法/其他解决方案。
所以问题是，给定一个像这样的括号字符串：

[[]]

我们想给每个括号分配一个组号（组1或组2）。有效的赋值意味着，如果只查看第一组中的方括号，它将形成一个有效的、平衡的方括号字符串（类似于[][[]]和不类似于]]][]的字符串）。第二组也是如此。组不必是连续的。我们想把这些括号分成两组。
在[[]]上面的示例字符串上，答案是6，下面是枚举数：（1=组1，2=组2）

  [[]]
1.1111
2.2222
3.1221
4.2112
5.1212
6.2121

这种安排不必包括所有的组（就像在安排1中一样）。以及2.）
思想
一个明显的暴力解决方案，可以很快地处理多达32个方括号，就是有一个32位整数，表示哪些方括号是单个组的一部分。或者我们可以使用数组。运行时是o（2^n）（我认为），这太慢了？
从问题的角度来看，我认为你得到的原始括号字符串必须是预平衡的，否则就没有办法选择一个子集，使组1和组2是平衡的。
我还注意到您可以分离组件—字符串“[]”有两种排列方式，因此字符串“[[]]有四种排列方式。（您可以找到每个组件中的方法数并将它们相乘）。
不过，我对如何将这些想法转化为算法感到困惑。我编写了蛮力程序，检查了字符串“[]”、“[[]]”、“[[[[]]]”和“[[[[]]”，但我没有看到真正的模式。
把这些字符串插入到我的暴力程序中，我得到：

"[]" = 2
"[[]]" = 6
"[[]]" = 20
"[[[[]]]]" = 70

代码：

char buf[1000];
int N;
bool isValid(int mask)
{
    int lv = 0;
    for (int i = 0; i < N; i++)
    {
        if (mask & (1 << i))
        {
            if (buf[i] == '(')
            {
                lv++;
            }
            else
            {
                lv--;
            }
            if (lv<0)
            {
                return false;
            }
        }
    }
    return lv==0;
}

int main() 
{
    scanf("%s", buf);
    N = strlen(buf);
    int ways = 0;
    for (int i = 0; i < (1 << N); i++)
    {
        if (isValid(i) && isValid(~i))
        {
            ways++;
        }
    }
    printf("Number of ways is %d\n", ways);
    return 0;
}

Answer 1

给出了C++中的O（n ^ 3）-时间，O（n ^ 2）-空间动态规划解。但是这个算法的合理性首先需要一些解释。在下面，我使用“substring”表示元素的有序子集必须是连续的，“subsequence”表示不需要的有序子集。
生成我们知道有效的字符串
将字符串的深度定义为它包含的[s个数减去]s个数。
让我们建立一些所有有效（“平衡”）括号字符串必须遵守的规则：
必须有相等数量的[s和]s。
字符串的前缀不能有负深度，即]s大于[s。
这些显然是必要的条件——如果一个字符串违反了任一规则，它就不能有效。但是为了能够方便地生成我们知道是有效的字符串，我们需要证明这些条件也足够：任何遵守这些规则的字符串都必须是有效的。为了帮助解决这个问题，让我们介绍一个引理：
引理：如果非空字符串服从条件（1）和（2），则它必须包含[]作为子字符串。
证明：它必须以[开头，否则length-1前缀包含的]s将多于[s并违反（2）。因此它必须至少包含一个]，否则将有i>=1[s和0]s，并且有效字符串必须包含相等数量的每个by（1）。因此，在j>1的某个位置必须出现第一个a]，其左边的字符必须是a[。
假设我们有一个服从条件（1）和（2）的非空字符串x。根据引理，它必须包含一个[]。删除此对不会导致违反这些条件中的任何一个，因此生成的字符串如果不是空的，则仍必须遵守条件（1）和（2），因此必须在某处包含[]。因此，我们可以继续删除[]s，直到留下空字符串为止。
在任何位置的有效字符串中插入[]都必须生成新的有效字符串，因为新的括号对总是相互匹配，并且不会干扰任何其他匹配的对。请注意，可以通过重复将xs插入空字符串（这是非常有效的）来构建原始字符串[]，其顺序与我们在上一段中删除它们的顺序相反：因此，我们现在已经证明x（即任何符合条件（1）和（2）的字符串）是有效的。
右递归
一种表达op问题的等价方法是：“我们可以用多少种方法来选择字符位置的有效子序列，以便剩余的子序列也有效？”如果我们首先将其概括为：
假设到目前为止我们选择的子序列具有depthd，而到目前为止我们未选择的子序列具有depthe，那么我们可以通过多少种方式从后缀中选择一个有效的子序列，从k位置开始，以便剩余的子序列也是有效的？
调用此函数count(d, e, k)。原来的问题现在的答案是count(0, 0, 0)。
事实上，我们可以通过注意d+e必须等于k字符后的总深度来进一步简化问题，因此我们可以从e和d中确定k，count()只需要两个参数。
此外，在测试是否可以选择空子序列时，我们只需要测试d==0。我们不需要费心测试e加上剩余的后缀在不低于它的情况下降到0，因为如果d==0，那么我们已经从原始字符串中减去了0的净深度（假设它是有效的，它必须以0的深度结束，而不低于0）。
为了递归地解决这个问题，我们需要从搜索所有可能的子序列的过程中分离出第一个决策点。长度为n的字符串的子序列必须属于以下n+1情况之一：它要么为空，要么具有最左边的元素，该元素可以是字符串中的n个字符中的任何一个。在做出第一个决定后通过递归产生的子序列都是不同的。
递归正常工作时，记住它很简单：只需在2d vectormemo[][]中记录任何给定调用的正确答案，2d vectorcount(d, k)最初由-1值填充。由于函数if (memo[d][k] == -1) {有两个参数，对于长度为n的字符串，其范围分别为0到n/2和0到n，因此需要o（n^2）空间，long long块的内部最多执行o（n^2）次。每当发生这种情况时，O（n）循环运行，将时间复杂度提高到O（n 3）。
实际代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class PartitionCounter {
    // Return the number of subsequences of the suffix of v beginning at position k
    // that are (a) valid, given that the initial depth of the subsequence is d (on
    // account of it being the suffix of some larger subsequence), and (b)
    // leave behind a remainder subsequence that is also valid, given that
    // the remainder sequence has initial depth depths[k]-d.
    int count(int d, int k) {
        // If a prefix of either sequence (selected or remaining) has more ']'s
        // than '['s then there can't be any completing subsequences.
        if (d < 0 || depths[k] - d < 0) {
            return 0;
        }

        // Only compute the answer if we haven't already.
        if (memo[d][k] == -1) {
            // A subsequence must either contain no elements, or a leftmost element
            // at some position.  All subsequences produced by recursion after this
            // initial choice are distinct (when considering the sequence of
            // character indices included, though not necessarily when considering
            // the sequence of characters themselves).

            // Try including no elements.  This effectively terminates the larger
            // subsequence that the selected subsequence is part of, so it can be
            // legal only if its depth is 0.  It also effectively includes all
            // remaining characters in the remainder sequence, but if the selected
            // subsequence has depth 0 and the original string does too, then it's
            // implied that the remainder must also have total depth 0, so we don't
            // need to check it.
            int n = (d == 0);

            // Try including a leftmost element at each remaining position.
            // If this would cause a remainder subsequence that has negative
            // depth, stop: any later loop iterations would also create illegal
            // remainder subsequences.
            for (int i = k; i < v.size() && depths[i] - d >= 0; ++i) {
                n += count(d + v[i], i + 1);
            }

            memo[d][k] = n;
        }

        return memo[d][k];
    }

    vector<int> v;          // 1 for '[', -1 for ']'
    vector<int> depths;     // depths[i] is the sum of the 1st i elements
    vector<vector<int> > memo;  // DP matrix.  -1 => not computed yet

public:
    PartitionCounter(string s) : memo(s.size() / 2 + 1, vector<int>(s.size() + 1, -1)) {
        depths.push_back(0);
        int total = 0;
        for (int i = 0; i < s.size(); ++i) {
            v.push_back(1 - 2 * (s[i] == ']')); // Map '[' to 1 and ']' to -1
            depths.push_back(total += v[i]);
        }
    }

    int count() {
        if (depths.back() == 0) {
            return count(0, 0);
        } else {
            return 0;       // Need to handle invalid strings specially
        }
    }
};

int main(int argc, char **argv) {
    PartitionCounter c(argv[1]);
    cout << c.count() << '\n';
}

结果

C:\>partitioncounter []
2

C:\>partitioncounter [[]]
6

C:\>partitioncounter [[[]]]
20

C:\>partitioncounter [[[[]]]]
70

C:\>stopwatch partitioncounter [][[[[[][][][][[][][]]]]]][]
10001208
stopwatch: Terminated. Elapsed time: 15ms
stopwatch: Process completed with exit code 0.

C:\>stopwatch partitioncounter [][[[[[][[[]][][][[]]][[][]]]]]][]
562547776
stopwatch: Terminated. Elapsed time: 0ms
stopwatch: Process completed with exit code 0.

当然，如果需要额外的位，您可以使用 int或其他方式代替 ]。
编辑：修正了石指出的错误。当我们跳过要从所选子序列中排除的字符时，余数子序列会累积它们。目前所发生的情况是，我们实际上只排除了在整个子序列上的 [s大于 s的余数子序列——但是为了避免违反条件（2），我们需要检查字符串的所有前缀是否都是这样。我们现在通过提前停止循环来实现这一点，这样就不会在第一时间生成这些违反余数的子序列。作为奖励，算法变得更快！：）