方針
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]; } }