hdu 1292（DP）

這道題有點兒難度，但是難度也只算一般，不明白一道漢語題目，意思簡單通俗易懂，結果提交量就那麼點兒。

考慮一支隊伍分組的數目，如果這支隊伍有n個人，就有n種情況分別是一個組，兩個組。。。。

i個人分成j組有兩種方式，一種是i-1個人分成j-1組之後，第i個人獨立分成一組，另一種情況是i-1個人分成j組，第i個人隨便加入j組中的任何一組，也都符合條件。狀態轉移方程為f[i][j]=f[i-1][j-1]+f[i-1][j]*j。直接將數據打表，計算結果的時候只要將i等於n的所有情況相加。

需要注意的是結果的值非常大，需要用__int64去存。

[cpp] #include<stdio.h>  
#include<string.h>  
#define N 30  
int main() 
{ 
    __int64 f[N][N]; 
    int i,j; 
    int n; 
    memset(f,0,sizeof(f)); 
    f[1][1]=1; 
    f[1][0]=0; 
    for(i=2; i<25; i++) 
    { 
        f[i][0]=0; 
        f[i][1]=1; 
        for(j=1; j<25; j++) 
        { 
            if(i==j) 
            { 
                f[i][j]=1; 
                continue; 
            } 
            f[i][j]=f[i-1][j-1]+f[i-1][j]*j; 
        } 
    } 
    int T; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d",&n); 
        __int64 sum; 
        sum=0; 
        for(i=1; i<=n; i++) 
            sum+=f[n][i]; 
        printf("%I64d\n",sum); 
    } 
    return 0; 
}