Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- long long getNthCatalan(int n, vector<long long> &memo){
- if(n == 0 || n == 1){
- return 1;
- }
- if(memo[n] != -1){
- return memo[n];
- }
- long long nthCatalan = 0;
- for(int i = 0, j = n - 1; i <= j; i++, j--){
- long long ithTerm = (long long) getNthCatalan(i, memo) * (long long) getNthCatalan(j, memo);
- nthCatalan += (i != j) ? 2 * ithTerm : ithTerm;
- }
- return memo[n] = nthCatalan;
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- vector<long long> memo(n + 1, -1);
- cout << getNthCatalan(n, memo) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
