动态规划：计算第k个括号序列

Question

一个n个括号的序列由n个“（”和n个“）”组成。

一个有效的括号序列定义如下：

你可以找到一种重复擦除相邻的括号“()”，直到变成空的方法。

例如，“（（））”是一个有效的括号，你可以擦除第2和第3个位置上的括号对“（）”，然后它变成“()”，最终变为空。 “）（”不是有效的括号，当你擦除第2和第3个位置上的括号对后，它变成“）（”，你不能再擦除任何括号。

现在，我们有所有有效的n个括号序列。在字典序中查找第k个最小序列。

例如，这里是所有有效的3个括号序列按字典顺序排序：

((()))
(()())
(())()
()(())
()()()

来源：https://code.google.com/codejam/contest/4214486/dashboard#s=p3

注意：比赛已结束，解决方案可供下载。

我已经使用C ++ STL中提供的next_permutation（）函数解决了小输入（k＜10^6）的问题。但我无法为此构思子问题。我尝试使用卡特兰数解决此问题，但似乎没有成功。我不想参考解决方案，因为那对学习没有帮助。请帮助我确定一个子问题。

- Harshil Lodhi

---

第一个闭括号在哪里？你有n/2个位置可以放置它。因此，你有u(n) = n/2 * u(n-2)。然后，你删除第一个“（）”子字符串并得到一个n-2有效序列。在这个子字符串中，第一个闭括号在哪里，你仍然有(n-2)/2个选择！依此类推。 - Rerito

Answer 1

让N表示序列的长度（即2 n）。

关键是能够计算长度为N的有效序列数量。

如果您有一个名为countValid(N, depth)的函数，可以按以下方式解决原始问题：

1. 如果depth < 0，则不可能（负深度表示无效序列） 2. 如果k < countValid(N-1, depth+1)，则追加(（因为所需序列位于剩余搜索空间的前半部分） 3. 否则追加)（因为所需序列位于总搜索空间的后半部分） 4. 如果选择了上面的(，则使用更新的N-1和depth+1继续执行1，如果选择了上面的)，则使用depth-1继续执行1。 countValid(N, depth)可以使用标准DP矩阵M实现动态编程，其中两个参数作为索引：

1. 基本情况下，M[0,0] = 1，因为有一个有效的0长度序列（空序列）。 2. 对于第一列中的所有其他值，M[0, 1...N]为0。 3. 对于M[N,depth]，您只需要加起来： - 开放后有效序列的数量：M[N-1, depth-1]，以及 - 关闭后有效序列的数量：M[N-1, depth+1] 即： M[N,depth] = M[N-1, depth-1] + M[N-1, depth+1]

- aioobe

---

@Rerito 你删除了你的回答。那种方法有问题吗？ - Harshil Lodhi

@Rerito 是的，n个括号表示长度为2n的序列。 - Harshil Lodhi

@HarshilLodhi，是的，我的递归关系显然是错误的！aioobe的方法才是你必须学习的。 - Rerito

@aioobe 我明白了，也许说明一下 n 和 depth 代表什么会帮助我们一眼看穿！我想我懂了 :) - Rerito

更新的答案。我不能依赖解决方案中的n，因为当深度为奇数时，奇数长度很重要。 - aioobe

Answer 2

我知道这是一个旧的帖子，但有些人可能会回到这里。我很难实现aioobe的解决方案，因为我认为它缺少了一步：

3.1) 如果您选择“)”，那么k = k - countValid(N-1, depth+1)

从直觉上讲，推理如下。如果您选择减小深度，则要查找的序列位于在(N,depth)处进行划分的搜索空间的第二部分中。如果我们保持k不变，那么在某个时刻沿着路径时，它将比所有剩余解决方案的数量都大，那么遍历就不再起作用了。我们需要减去我们在遍历矩阵时排除的解决方案数量，以产生所需的结果。

以下是一些Java代码，用于查找包含每个（N，depth）的有效序列数的矩阵D中的第k个元素：

// get k-th element
int N = 2*n;
int d = 0;
String str = new String("");
while (N>0 && d >= 0) {
  // invalid elements (out of bounds or 0)
  if (d+1 > n || D[N-1][d+1] == 0) {
    str += ")"; d--;
  } else if (d-1 < 0 || D[N-1][d-1] == 0) {
    str += "("; d++;
  } else {
    if (k <= D[N-1][d+1]) {
      // first part of search-space
      str += "("; d++;
    } else {
      // second part of search-space
      str += ")";
      k -= D[N-1][d+1]; // substract number of excluded solutions
      d--;
    }
  }
  N--;
}

// For valid strings k should be 1
if (k != 1) str = "Doesn't Exist!";

- Nils Hammerla