動態規劃：計算第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個括號序列

回答

相關問題