1259. Handshakes That Don’t Cross

You are given an even number of people numPeople that stand around a circle and each person shakes hands with someone else so that there are numPeople / 2 handshakes total.

Return the number of ways these handshakes could occur such that none of the handshakes cross.

Since the answer could be very large, return it modulo 109 + 7.

class Solution {
    vector<long> dp;
    int mod = 1e9 + 7;
    long solution(int n) {
        if(n == 0) return 1;      
        if(dp[n/2] != 0) return dp[n/2];
        long& res = dp[n/2];
        for(int i = 0; i < n; i += 2) {
            res = (solution(i) * solution(n - i - 2) % mod + res) % mod;
        }
        
        return res;
    }
public:
    int numberOfWays(int numPeople) {
        dp = vector<long>(numPeople / 2 + 1, 0);
        return solution(numPeople);
    }
};