FilesExpand file tree

 master

/

Catalan_Number.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (43 loc) · 912 Bytes

 master

/

Catalan_Number.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (43 loc) · 912 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

/*

Task : Catalan_Number

Author : Borworntat D. [Hydrolyzed~]

School : RYW

Language: C++

Created : 03 May 2021 [13:32]

*/

#include<bits/stdc++.h>

#define all(x) begin(x),end(x)

#define sz(x) (int)(x).size()

using namespace std;

using LL = long long;

using PII = pair<int ,int >;

using PLL = pair<long long ,long long >;

const int dir4[2][4] = {{1,-1,0,0},{0,0,1,-1}};

const int dir8[2][8] = {{-1,-1,-1,0,1,1,1,0},{-1,0,1,1,-1,0,1,-1}};

const int N = 10010;

int dp[N];

int catalan_topdown(int n){

if(dp[n] != -1){

return dp[n];

}

if(n <= 1){

return dp[n] = 1;

}

int ret = 0;

for(int i=0; i<n; ++i){

ret += catalan_topdown(i) * catalan_topdown(n - i - 1);

}

return dp[n] = ret;

}

int catalan_bottomup(int n){

dp[0] = 1;

for(int i=1; i<=n; ++i){

for(int j=0; j<i; ++j){

dp[i] += (dp[j] * dp[i - j - 1]);

}

}

return dp[n];

}

void initial_for_topdown(){

memset(dp, -1, sizeof dp);

}