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