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

有效括号序列定义为以下：

可以找到一种方式来重复擦除相邻对括号“（）”，直到它变空。例如，“（（））”是一个有效的圆括号，您可以在第二和第三个位置擦除该对，然后它变为“（）”，然后您可以将其设为空。（）“（）（”不是一个有效的括号，在你擦除第二和第三个位置上的对之后，它就变成了“）（”并且你不能再擦除

现在，我们有全部有效的括号。序列查找字典顺序第k个最小序列

例如，以下是字典顺序所有有效3个括号序列：

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

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

注：比赛在现在在...之上nd解决方案可供下载。

我已经通过使用在C++ STL中可用的next_permutation（）解决了它的小输入问题（k ）。我无法为此制定一个小问题。我试图通过使用加泰罗尼亚号码解决这个问题，但似乎没有取得任何成功。我不想看到解决方案，因为它不利于学习。请帮助我确定一个子问题。

来源

2014-10-18 Harshil Lodhi

哪里第一闭括号？你有'n/2'的位置可以容纳它。因此，你有'u（n）= n/2 * u（n-2）'。然后删除第一个“（）”子串并获得一个“n-2”有效序列。这个子字符串中的第一个右括号在哪里，你仍然有'（n-2）/ 2'选择！等等。 – Rerito 2014-10-18 07:29:23

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

关键是能够计数有效序列长度的数目否。

如果你有一个函数，countValid（ñ，深度），你可以按如下解决原来的问题：

如果深度 < 0这是不可能的（负深度指无效序列）
如果k < countValid（Ñ -1，深度 1）追加(（因为寻求序列位于剩余的搜索空间的前半部分）
否则附加)（因为寻求序列在于总搜索空间的下半场）
从1继续与更新ñ -1和深度 1如果选择(上方或深度 -1如果您选择上面的)。

countValid（Ñ，深度）可以与用标准DP矩阵动态编程实现，中号，用两个参数为指标：

基本情况下，M [0,0] = 1，因为有一个有效长度为0的序列（空序列）
对于在第一列中号 [0,1 ... Ñ]为0的所有其它值。
对于中号 [Ñ，深度]你只是加起来
- 有效序列的开口之后的数：中号 [Ñ -1，深度 - 1]和
- 收盘后有效序列号：M [Ñ -1，深度 1]
是：中号 [Ñ，深度] = 中号 [Ñ -1，深度 -1] + 中号 [ñ -1，深度 1]

来源

2014-10-18 07:18:55 aioobe

有效的序列只能是偶数的。所以我猜你的意思是'2.n'而不是'n'的长度？ – Rerito 2014-10-18 08:06:40

@Rerito你删除了你的答案。这是他们的问题吗？ – 2014-10-18 08:07:15

@Rerito有n个圆括号表示长度为2n的序列 – 2014-10-18 08:07:50

我知道这是一条古老的线索，但有些人可能会回来。我有一个很难实现aioobe的解决方案，因为我认为它忽略了一步：

3.1），如果选择 “）”，则K = K - countValid（N-1，深度+ 1）

直观推理是这样的。如果您选择减小深度，则您要查找的序列位于搜索空间的第二部分（N，深度处）。如果我们保持k相同，它将沿着路径的某个点比所有剩余的解决方案的数量更大，并且我们的遍历不再起作用。我们需要减去我们排除的方法遍历矩阵的次数，以产生所需的结果。

这里是如果有包含有效序列的数目为每个（N，深度）矩阵d求出第k个元素一些Java代码：

// 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!";

来源

2015-10-06 08:54:44

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

回答

相关问题