sorry, mistakes in boundaries, correct as below: if (n>m) then C(m,n) = 0; for each m in {1,2...N}, C(m,1) = m;
On Wed, Sep 8, 2010 at 11:22 AM, Adam <wangyanadam1...@gmail.com> wrote: > 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 <gene.ress...@gmail.com> 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 <harihari1...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.