## 把整数`N`转化成k个严格递增正整数整数序列`n1, n2, …, nk`的和，请问有多少种情况？

``````若n > m：f(n, m) = f( n-m, m-1 ) + f( n, m-1 )

``````

``````f( 1, 1 ) = 1
f(i,1) = 0 其中i>1
``````

``````#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

enum { max_len = 501 };
double cases[max_len][max_len];

class StairCases
{
public:
StairCases() { init(); }

double get_num(int n)
{
return lookup(n, n) -1;
}

private:
double lookup( int n, int m )
{
if ( cases[n][m] >= 0 )
{
return cases[n][m];
}
if ( n==1 && m==1 )
{
return cases[n][m] = 1;
}

if ( n>1 && m==1 )
{
return cases[n][m] = 0;
}

if ( n <= m )
{
return cases[n][n] = 1+lookup( n, n-1 );
}
else // n>m
{
return cases[n][m] = lookup(n-m, m-1) + lookup(n, m-1);
}
}

void init()
{
for ( int i=1; i<max_len; ++i )
{
for ( int j=1; j<max_len; ++j )
{
cases[i][j] = -1;
}
}

for ( int i=2; i<max_len; ++i )
{
cases[i][1] = 0;
}
cases[1][1] = 1;
}
};

int main()
{
StairCases sc;
int n;
while ( cin >> n && n  )
{
printf( "%.0f\n", sc.get_num(n) );
}
return 0;
}
``````

## 将一个正整数n表示成一系列正整数之和，`n = n1 + n2 + … + nk`，其中`n1 >= n2 >= … >= nk >= 1`.求整数n的划分个数，并展示这些划分。

``````若n > m：f(n,m) = f(n-m,m) + f(n,m-1) (对应最大值为m和小于m两种情况)

f(1,n) = 1
``````

``````#include <iostream>
#include <vector>
using namespace std;

typedef vector< vector<int> > split_vect;

split_vect split( int n, int m )
{
if ( n==1 )
{
vector<int> cur( 1,1 );
return split_vect( 1, cur );
}

if ( m==1 )
{
vector<int> cur( n,1 );
return split_vect( 1, cur );
}

if ( n <= m )
{
split_vect ret( 1, vector<int>(1,n) );
split_vect const& tmp_ary = split( n,n-1 );
ret.insert( ret.end(), tmp_ary.begin(), tmp_ary.end() );
return ret;
}
else // n > m
{
split_vect ret;
split_vect tmp_ary1 = split( n-m,m );
for ( int i=0; i<(int)tmp_ary1.size(); ++i )
{
tmp_ary1[i].push_back( m );
}
split_vect const& tmp_ary2 = split( n,m-1 );
ret.insert( ret.end(), tmp_ary1.begin(), tmp_ary1.end() );
ret.insert( ret.end(), tmp_ary2.begin(), tmp_ary2.end() );
return ret;
}
}

void print( vector<int> const& v )
{
for ( int i=0; i<(int)v.size(); ++i )
{
cout << v[i] << " ";
}
cout << endl;
}

int main()
{
split_vect const& ret = split(8, 8);
cout << "kinds: " << ret.size() << endl;
for ( int i=0; i<(int)ret.size(); ++i )
{
print( ret[i] );
}
return 0;
}
``````