You are not logged in. Please login at www.codechef.com to post your questions!

×

Dynamic Programming (Hackerrank WalmartLabs-codesprint)

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

asked 04 Nov '16, 13:11

akchamp's gravatar image

4★akchamp
12419
accept rate: 20%

edited 04 Nov '16, 13:12


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;
          }
      }
}
link

answered 04 Nov '16, 13:41

tapanr97's gravatar image

4★tapanr97
161
accept rate: 25%

edited 04 Nov '16, 13:50

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

diveshuttam's gravatar image

3★diveshuttam
53718
accept rate: 27%

edited 04 Nov '16, 14:18

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

epsilonalpha's gravatar image

3★epsilonalpha
7015
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,085

question asked: 04 Nov '16, 13:11

question was seen: 1,088 times

last updated: 04 Nov '16, 20:45