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();
}