Google Codejam 亚太地区测试练习轮：括号顺序

我花了一天时间解决这个问题并且找不到传递大型数据集的解决方案。

Problem

n 个括号序列由 n 个“(”和 n 个“)”组成。

现在，我们有了所有有效的 n 个括号序列。找到第 k 个最小的序列词典编纂的 order.

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

((()))

(()())

(())()

()(())

()()()

给定 n 和 k，编写一个算法来给出第 k 个最小序列词典编纂的 order.

对于大数据集：1 ≤ n ≤ 100 and 1 ≤ k ≤ 10^18

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

• Let 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 左括号 and 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
  

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