http://acm.timus.ru/problem.aspx?space=1&num=1017

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxn 600 5 using namespace std; 6  7 __int64 dp[maxn][maxn]; 8  9 int main()10 {11     int n;12     scanf("%d",&n);13     memset(dp,0,sizeof(dp));14     dp[1][1]=1;15     for(int i=2; i<=n; i++)16     {17         for(int j=1; j<=i; j++)18             dp[i][j]=dp[i-1][j-1]+dp[i-j][j-1];19     }20     __int64 sum=0;21     for(int i=0; i!=n; i++) sum+=dp[n][i];22     printf("%I64d\n",sum);23     return 0;24 }