Google codejam APAC测试练习轮:圆括号顺序

Question

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

问题

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

现在,我们拥有所有有效的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
  

  请注意,开放括号在字典顺序中小于紧括号,因此我们总是首先尝试添加开括号.