Share
Report
5Let C(n, d) count the number of balanced parenthetical strings of length exactly n and nested depth at most d. So for instance:
()(()) has length 6 and depth 2
(())((()(()))) has length 14 and depth 4
Is there any easy recursive relation on counting C(n, d) that one can use for dynamic programming. The base cases are clear:
C(n, d) = 0 if n is odd.
C(n, d) = 0 if d = 0 and n > 0
C(n, d) = 1 if n =0 and d= 0 (the empty string)
But what about otherwise?
I think something of the form
sum_{i <= n, j <=i/2} C(i, j)C(n-i, d-j) will eventually cover all possible strings (basically we're mixing strings of length i with strings of length n -i) but I'm pretty sure we suffer from a lot of overcounting here.
Is there a good recurrence relation for this, and if so, what would the runtime be like if implemented via dynamic programming?
All responses (
Answers (
