題意:
(from luckycat)
解法: DP，對於某任何一種括號情況，我們都可以將最左邊的 "(" 以及與它配對的右括號拉出來看，可以寫成 "(A)B" ，若括號串長度為 n ，且題目給的 n 必是偶數(合法括號情況)，所求深度為 d ，則我們可以定義遞迴方程，為求方便我們令 m = n/2，假設 dp[m][d] 代表總共有 m 對括號且深度不大於 d 的狀況總數，將當前括號情況看成 "(A)B" 的話，則發現 A 的深度不能大於 d-1，B 的深度不能大於 d ，再枚舉 A 的長度來求出當前的所有情況數，而最後我們要求的是深度剛好等於 d ，所以最後要的答案是 dp[n/2][d] - dp[n/2][d-1]。
遞迴方程
dp[m][d] =
{ 1, if m = 0 & d >= 0
{ 0, if m > 0 & d = 0
{ sum( dp[k][d-1]*dp[m-k-1][d], 0 <= k < m ), if m > 0 & d > 0
TAG: DP, BigNum
注意: 需要用大數
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽