HDU 2512 一卡通大冒险

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2512

//dp[i][j] 表示i个卡片分成j组 由两种状态转移过来
//一：第i个卡片单独分成一组，那有dp[i-1][j-1]种
//二：第i张牌与其他组任意一组夹在一块，i-1张牌就得分成j组，那就是dp[i-1][j]种乘上个j，即dp[i-1][j]*j种
//处理边界情况：多个牌分成一组的话 dp[i][1] = 1，多个牌分成同样多组的话 dp[i][i] = 1
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[2005][2005];
int main()
{
    for(int i = 1 ; i <= 2000 ; ++i) {
        for(int j = 1 ; j <= i ; ++j) {
            if(i == j || j == 1)
                dp[i][j] = 1;
            else
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * j) % 1000;
        }
    }
    int t , n;
    scanf("%d" , &t);
    for(int ca = 1 ; ca <= t ; ++ca) {
        scanf("%d" , &n);
        int res = 0;
        for(int i = 1 ; i <= n ; ++i)
            res = (res + dp[n][i]) % 1000;
        printf("%d
" , res);
    }
}