Question

Can someone please explain the dynamic programing solution to this problem.

Accepted Answer

This problem can be solved by knowledge of 'Catalan Number'. You can read on this: http://www.geeksforgeeks.org/applications-of-catalan-numbers/ and https://en.wikipedia.org/wiki/Catalan_number . Here is dynamic solution to find n'th catalan number:

long long int catalan[4002];
void precalc()
{
      catalan[0] = 1;
      for(int i=1;i<=4001;i++)
      {
          if(i==1)
                catalan[i] = 1;
          else
          {
                long long int sum =0,left,right;
                for(int k=0;k<i;k++)
                {
                      left = catalan[k]%MOD;
                      right = catalan[(i-1)-k]%MOD;
                      sum = (sum + (left*right)%MOD)%MOD;
                }
                catalan[i] = sum;
          }
      }
}

Answer 2

2

You could also check out this article on catalan numbers.As catalan numbers are defined recursively it can be easily converted into itarative dp(similar to fibonacci).Just undestand how we arrive at the series coding this into dp is quite intutive. for solution you may refer to geeksforgeeks.

link

answered 04 Nov '16, 14:07

4★diveshuttam
537●1●8
accept rate: 27%

edited 04 Nov '16, 14:18

Answer 3

0

This was the function I used in Java:

static long[] catalanDP(int n)
    {
        long[] f = new long[n+1];
        f[0] = f[1] = 1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<i;j++)
                f[i] = (f[i] + (f[j] % MOD * f[i-1-j] % MOD)) % MOD;
        }

        return f;
    }

link

answered 04 Nov '16, 20:45

3★epsilonalpha
105●1●6
accept rate: 28%

Dynamic Programming (Hackerrank WalmartLabs-codesprint)

Follow this question

Related questions