[13699번] 점화식 - Dynamic Programming 동적계획법[C++]

이 문제는 동적계획법으로 푸는 문제로

시간초과는  memoization으로 해결하면 되고

딱히 큰 어려움은 없는 문제이다.

#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[36];
 
unsigned long long t(int n) {
    if (n == 0)
        return result[n] = 1;
    if (result[n] > 0)
        return result[n];
    else {
        for (int i = 0; i < n + 1; i++)
            result[n] += t(i)*t(n - i - 1);
        return result[n];
    }
}
 
int main() {
    int input;
    cin >> input;
    cout << t(input);
    return 0;
}