There is my version of DP:
Define C(m,n) as the number of proper bracket expressions
B1,B2,B3,...,Bm+n with m left brackets '(' and n right brackets ')',
in which 'proper' means that for each i belonging to {1,2,...,m+n} the
number of left brackets '(' in B1,B2...Bi is larger than or equal to
the number of right brackets ')' in it. The goal is to figure out
C(N,N), where N is the given positive number.
For example, m = 2 & n = 1, then '(()' and '()(' are all proper
expressions.
First we try to find the boundaries:
if (n>m) then C(m,n) = 0;
for each n in {1,2...N}, C(1,n) = 1;
for each m in (1,2...N), C(m,1) = m;
Then we try to find the recursive relations:
if (m+n is in {S1,S2...Sk}) then C(m,n) = C(m-1,n);
if (m+n is not in {S1,S2...Sk}) then C(m,n) = C(m-1,n) + C(m,n-1);
The goal is to compute C(N,N).
On Sep 7, 8:45 pm, Gene <[email protected]> wrote:
> This is a nice problem. The trick is always defining the recurrence
> in an artful way.
> Here let E(L, e) be the number of bracket expressions of length L that
> are proper _except_ that there are e extra left brackets.
>
> So for L = 1 and 0 <= e <= n, we have
>
> E(1, e) = (e == 1) ? 1 : 0
>
> That is, the only unit length proper bracket expression possibly
> having extra left brackets is a single left bracket. It obviously has
> exactly 1 extra left bracket.
>
> Say S = { s1, s2, ... sk}. If k < n, then k locations are "fixed" as
> left brackets. All the others can potentially be either left or
> right.
>
> E(L, e) = (L \in S) ? E(L - 1, e - 1) : // only "[" allowed at L'th
> position
> E(L - 1, e - 1) + E(L - 1, e + 1) // "[" or "]" allowed
>
> To make this complete, we need to add E(L, e) = 0 for any
> e < 0 or e > n
> because in these cases no proper bracket expressions exist.
>
> Finally we get the answer: E(2n, 0)
>
> So for fun, let's suppose the set S is empty and we want to know the
> answer for the case n=3, which is L=6.
>
> We have
> e = 0 1 2 3
> L = 1: 0 1 0 0
> 2: 1 0 1 0
> 3: 0 2 0 1
> 4: 2 0 3 0
> 5: 0 5 0 3
> 6: 5 0 8 0
>
> The answer is E(6,0) = 5 corresponding to
> [[[]]], [[][]], [][[]], [[]][], and [][][].
>
> Now let's say S = { 5 }. There are only 2 of the 5 expressions with
> "[" in the 5th position. And we have:
>
> e = 0 1 2 3
> L = 1: 0 1 0 0
> 2: 1 0 1 0
> 3: 0 2 0 1
> 4: 2 0 3 0
> 5: 0 2 0 3
> 6: 2 0 5 0
>
> So we have E(6,0) = 2 as expected.
>
> On Sep 7, 4:22 am, hari <[email protected]> wrote:
>
> > You are given:
>
> > * a positive integer n,
> > * an integer k, 1<=k<=n,
> > * an increasing sequence of k integers 0 < s1 < s2 < ... < sk <=
> > 2n.
>
> > What is the number of proper bracket expressions of length 2n with
> > opening brackets appearing in positions s1, s2,...,sk?
> > plz.. explain how to solve this problem
>
> > thanks in advance
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
