# URAL1017[The Staircases]

f[n][i]=N分堆后最大的为i一共有几种分法
f[n][n]=1
f[n][i]=sum{f[n-i][j],1<=j<i<n}
(减一是减去只有一堆的情况)
CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-16

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int N;

public:

Application()

{

cin>>N;

}

int run()

{

//N分堆，每堆不同，一共有多少分法？

//f[n][i]=N分堆后最大的为i一共有几种分法

//f[n][n]=1

//f[n][i]=sum{f[n-i][j],1<=j<i<n}

vector<vector<long long int> > f(N+1,vector<long long int>(N+1,0));

for (int i=1;i<=N;i++) f[i][i]=1;

for (int n=1;n<=N;n++)

for (int i=1;i<n;i++)

for (int j=1;j<i;j++)

f[n][i]+=f[n-i][j];

for (int i=1;i<=N;i++)

return 0;

}

};

int main()

{

Application app;

return app.run();

}