TopCoder SRM 363 Div1 Easy HandsShaking

問題

n人がテーブルに座って握手をする。
それぞれの人は他のただ一人と握手する。


全員が握手をしていて、かつ手が一本も交差していないとき、握手の仕方を良いと呼ぶ。
良い握手の仕方は何通りあるか、求めよ。

制約条件

n≦50

方針

動的計画法による。
dp[i]をi人がする良い握手の場合の場合の数とすると、
一人が左からj番目の人と握手をするときの場合の数は
dp[j-1]*dp[i-j-1]通りとなり、これは同じ問題のサイズの小さいものになっている。


したがってdp[i]を小さいほうから埋めていくようなDPにより、
O(n^2)で答えが求まる。

ソースコード

class HandsShaking {
  public:
  long long countPerfect(int n) {
    ll dp[51]={};
    dp[0]=1;
    for(int i=2;i<=n;i++){
      for(int k=1;k<i;k++)dp[i]+=dp[k-1]*dp[i-k-1];
    }
    return dp[n];
  }
};