algorithm - Google codejam APAC 测试练习轮 : Parentheses Order

Question

我花了一天时间解决 this problem并且无法找到传递大型数据集的解决方案。

问题

n个括号序列由n个"("s和n个")"组成。

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

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

((()))

(()())

(())()

()(())

()()()

给定 n 和 k，编写一个算法以按字典顺序给出第 k 个最小的序列。

对于大数据集:1 ≤ n ≤ 100 和 1 ≤ k ≤ 10^18

Answer 1

这个问题可以用动态规划来解决

• 让dp[n][m] = 如果我们有 n，可以创建的有效括号数打开括号和 m关闭括号。
• 基本案例:
  dp[0][a] = 1 (a >=0)
• 使用基本情况填充矩阵:
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0 );

然后，我们可以慢慢构建第 k 个括号。

• 以a = n 个左括号和b = n 个右括号开头，当前结果为空

  while(k is not 0):
       If number dp[a][b] >= k: 
              If (dp[a - 1][b] >= k) is true:
                 * Append an open bracket '(' to the current result
                 * Decrease a 
              Else:
                 //k is the number of previous smaller lexicographical parentheses
                 * Adjust value of k: `k -= dp[a -1][b]`,
                 * Append a close bracket ')' 
                 * Decrease b
       Else k is invalid
  

  请注意，按字典顺序，左括号小于右括号，因此我们总是尝试先添加左括号。