Intersecting Chords in a Circle

• Time : $O(n^2)$
• Space : $O(n)$

int Solution::chordCnt(int A) {
    vector<long long> dp(max(3,A + 1));
    dp[0] = dp[1] = 1;
    dp[2] = 2;
    long long mod = 1e9 + 7;
    for(int i = 3; i <= A; i++) {
        for(int j = 0; j < i; j++) {
            dp[i] = (dp[i] + dp[i - j - 1] * dp[j] % mod) % mod;
        }
    }

    return dp[A];
}