hdu一卡通大冒険递推或dp

タイトルリンクアドレス
この問題は私にdpの思想を感じさせます実はまた繰り返して帰ってくる途中で突然霊感があって後ろの1つの状態が前の1つの状態と関係があることを発見します
次のキーコードです

    a[1][1]=1;
    a[2][1]=1;
    a[2][2]=1;
    for(int i=3;i<=2000;i++){
       for(int j=1;j<=i;j++){
           if(j==1)a[i][j]=a[i-1][j];
           else {
              if(j==i)a[i][j]=(a[i-1][j-1])%1000;
              else a[i][j]=(a[i-1][j]*j+a[i-1][j-1])%1000;     
           }       
       }        
    }
    

例を挙げると、前の下の配列の1つはカード数の2つは分の数を表しているので、前の結論で後の結論を脱退することができます.
具体的には
a[2][1] ={AB} a[2][2]={A,B}
a[3][1]={ABC}     a[3][2]={AB,C}{AC,B}{A,BC}
3枚のカードが2枚のカードよりも数が多くなったので3枚目のカードの配置問題はABCを一組に入れることができるのはa[2][1]->a[3][1]で、それからa[2][1]の基礎の上で分けて開放してa[3][2]の中の{AB,C}を得て、それからa[2][2]が2組なので3枚目のカードはこの2組の中の任意の1組に置くことができて、{AC,B}{A,BC}を得ました
次はACコードです.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int a[2010][2010];
int main()
{
    a[1][1]=1;
    a[2][1]=1;
    a[2][2]=1;
    for(int i=3;i<=2000;i++){
       for(int j=1;j<=i;j++){
           if(j==1)a[i][j]=a[i-1][j];
           else {
              if(j==i)a[i][j]=(a[i-1][j-1])%1000;
              else a[i][j]=(a[i-1][j]*j+a[i-1][j-1])%1000;     
           }       
       }        
    }
    
     
    
    int n;
    scanf("%d",&n);
    while(n--){
       int edge;
       scanf("%d",&edge);           
       int sum=0;
       for(int i=1;i<=edge;i++){
           sum=(sum+a[edge][i])%1000;      
       }
       cout<<sum<<endl;        
    }
    
    
    
    return 0;    
}