PKU 1671 Rhyme Schemes
http://poj.org/problem?id=1671
N個のものを区別して、区別しないグループに分ける時の分け方の総数を求める。
メモ化再帰しました。
double dp[1010][1010]; int vis[1010][1010]; double rec(int n,int b){ if(b<1)return 0; if(n==b)return 1; if(n<1)return 0; if(vis[n][b])return dp[n][b]; vis[n][b]=true; return dp[n][b]=rec(n-1,b)*b+rec(n-1,b-1); } int n; void solve(){ double ans=0; for(int i=1;i<=n;++i) ans+=rec(n,i); printf("%d %.0f\n",n,ans); } main(){ while(cin>>n,n) solve(); }