整理分析了将一个正整数分解成特定的整数和的问题。

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

设函数 f( n, m )表示n的递增序列和式中最大值小于等于m的数量。那么，如果n分解的最大值为m，则有f( n-m, m-1 )种；最大值小于m，则有f(n, m-1)种。

则有：

若n > m：f(n, m) = f( n-m, m-1 ) + f( n, m-1 )
若n <= m：f(n, m) = f(n, n) = 1 + f(n,n-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的划分个数，并展示这些划分。

分析：设f(n,m)为n的不同的划分中，最大加数小于等于m的个数。则有，

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

初始值：f(n,1) = 1, n>=1
       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;
}