谷歌codejam APAC測試練習輪：括號令

我花了一天的時間解決this problem，並找不到解決方案來通過大型數據集。谷歌codejam APAC測試練習輪：括號令

問題

的n括號序列由n個「（」 s和n 「）」秒。

現在，我們有所有有效的n個括號序列。在詞典的順序中查找第k個最小序列。

例如，這裏是在詞典編纂順序所有有效3個括號序列：

((())) 

(()()) 

(())() 

()(()) 

()()()

鑑於n和k，寫的算法，得到第k個最小序列辭書順序。

對於大型數據集：1 ≤ n ≤ 100和1 ≤ k ≤ 10^18

來源

2014-09-22 Danny

有啥你的問題的有效後綴Y的數量？ – 2014-09-22 10:01:38

@WimOmbelets 我想，該算法解決上述問題 – Haris 2014-09-22 10:03:26

這個問題可以通過使用動態規劃

讓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

注意，開括號小於詞典編纂順序靠近支架，所以我們總是嘗試首先添加開放的支架。

來源

2014-09-22 10:34:29

什麼是基礎的情況下填充有效括號的數量？ – fex 2014-09-22 11:44:04

@fex更新了基本案例。 – 2014-09-22 11:50:37

謝謝你的算法。我跑了它，它是正確的。但是dp [n] [m]的含義（如果我們有n個開放括號和m個緊接的括號，可以創建有效括號的數目）會讓我感到困惑。如果n！= m，我們如何得到有效的括號？我不太明白dp [n] [m]的含義。 – Danny 2014-09-22 12:51:04

讓S= any valid sequence of parentheses from n(and n)。現在任何有效的序列S可以寫成S=X+Y其中

X=valid prefix也就是說，如果遍歷X從左至右，在任何時間點，numberof'(' >= numberof')'
Y=valid suffix即如果從右到穿越Ÿ離開，在任何時間點，numberof'(' <= numberof')'

對於任何S許多對X和Y是可能的。

在我們的例子：()(())

`()(())` =`empty_string +()(())` 
     = `(+)(())` 
     = `() + (())` 
     = `()(+())` 
     = `()((+))` 
     = `()(() +)` 
     = `()(()) + empty_string`

注意，當X=empty_string，然後從n個(數量的有效S和n ) =有效後綴Y的從n個(和數n )

現在，算法如下：我們將從X= empty_string開始並遞歸增長X直到X=S。在任何時候，我們有兩個選擇成長X，要麼追加 '（' 或追加 '）'

讓dp[a][b]= number of valid suffixes using a '(' and b ')' given X

nop=num_open_parenthesis_leftncp=num_closed_parenthesis_left

`calculate(nop,ncp) 
{ 
    if dp[nop][ncp] is not known 
    { 
    i1=calculate(nop-1,ncp); // Case 1: X= X + "(" 
    i2=((nop<ncp)?calculate(nop,ncp-1):0); 
/*Case 2: X=X+ ")" if nop>=ncp, then after exhausting 1 ')' nop>ncp, therefore there can be no valid suffix*/ 
    dp[nop][ncp]=i1+i2; 
    } 
    return dp[nop][ncp]; 
}`

讓我們例如，n = 3即3 (和3 ) 現在開始X=empty_string，因此

dp[3][3] =使用3 (和有效序列S數3 ) = 3 (和3 )

來源

2014-10-25 22:58:37

谷歌codejam APAC測試練習輪：括號令

回答

相關問題