29 Nov 2011
This is a problem posed by my girlfriend's boss at NovaLeaf.
The problem is:
Given n brackets, how many are the combination of valid brackets? For example, 2 brackets have  and [].
It's obvious that we can go after a brute-force method that looks like this:
def count(k, m) # k = number of opens, m = number of unuseds return 1 if k == 0 and m == 0 r = 0 r = r + count(k-1, m) if k > 0 # add closed bracket r = r + count(k+1, m-1) if m > 0 # add opened bracket return r end puts count(0, n) # result of n brackets
However, that kind of solution will never ever work at the level of TopCoder.com or Google CodeJam.
Of course, we need a dynamic-programming approach to count it efficiently.
Let say a a a … a[2n] is the valid positioning of n brackets.
The critical point for a dynamic-programming approach is to see that you do not need all the information to solve the problem.
For example, I finish a[i], use m brackets, and have k opened brackets. What I need to know to count is how many of a[i+1]…a[2n], use n-m brackets, and have k closed brackets are there.
And that's it.
Let's formulate the dynamic-programming approach to this problem:
Let a a ... a[2n] be the sequence of ( and ) d[i, k, m] is the number of combinations that have k opened brackets and use m brackets. The answer is d[2n, 0, n] The base case is d[1, 1, 1] = 1 The general case is d[i, k, m] = 0 d[i, k, m] += d[i-1, k+1, m] d[i, k, m] += d[i-1, k-1, m-1]
The explanation is:
At (i, k, m), it can come from closing one more brackets, which is from (i-1, k+1, m). Or, it can come from opening one more brackets, which is from (i-1, k-1, m-1).