SRM363 Div2 Mid

方針
DPで各マスに到達できる場合の数を数えていけばいいのですが、まだDPで解けばいいということに気付けません。。
この問題の答えはカタラン数になるそうです。
ソースコード

using System;
using System.Collections.Generic;
using System.Text;
 
public class HandsShaking
{
    public long countPerfect(int n)
    {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[2] = 1;
        for(long i = 4;i <= n;i += 2)
        {
            long ci = 0;
            for(long j = 2;j <= i;j += 2)
                ci += dp[j - 2] * dp[i - j];
            dp[i] = ci;
        }
        return dp[n];
    }
}