Лесенка - динамическое программирование

#include <fstream>
 
using namespace std;
 
int main()
{
    fstream fin;
    int n;
    fin.open("input.txt", ios::in);
    fin >> n;
    fin.close();
    
    int a[101][101];
    
    for (int cn = 1; cn <= n; cn++)
        a[cn][0] = 0;
    for (int cm = 0; cm <= n; cm++)
        a[0][cm] = 1;
        
    for (int cn = 1; cn <= n; cn++)
    {
        for (int c = 1; c <= cn; c++)
            a[cn][c] = a[cn][c - 1] + a[cn - c][c - 1];
        for (int c = cn + 1; c <= n; c++)
            a[cn][c] = a[cn][cn];
    }
    
    fstream fout;
    fout.open("output.txt", ios::out | ios::trunc);
    fout << a[n][n];
    fout.close();
    return 0;
}

//////////////////
long countStaircases (long numberPieces, long piecesInUpperLayer){
 
    long myPeaces;
    long peacesDown;
    long retVal = 0;
    if (numberPieces > piecesInUpperLayer){
        retVal++;       // we can make at least one variant (all pieces in line in one layer)
        myPeaces = piecesInUpperLayer+1;
        peacesDown = numberPieces-myPeaces;
        while (peacesDown > myPeaces){
            retVal += countStaircases (peacesDown--, myPeaces++);
        }
    }
    return retVal;
}

call:
 
std::string str;
long n = getStaircases (8, 0, &str, NULL);
 
//////////////////
long getStaircases (long numberPieces, long piecesInUpperLayer, std::string *pStaircaseStr, std::string *pPrefixStr){
 
    char buffer [64];
 
    long myPeaces;
    long peacesDown;
    long retVal = 0;
    std::string staircaseStr;
    std::string myPrefixStr;
    pStaircaseStr->clear();
    if (numberPieces > piecesInUpperLayer){
        retVal++;       // we can make at least one variant (all pieces in line in one layer)
        if (pPrefixStr != NULL){
            *pStaircaseStr = *pPrefixStr;
            myPrefixStr = *pPrefixStr;
        }
        ::sprintf (buffer, "%u", numberPieces);
        *pStaircaseStr += buffer;
        myPeaces = piecesInUpperLayer+1;
        peacesDown = numberPieces-myPeaces;
        while (peacesDown > myPeaces){
            if (pPrefixStr != NULL){
                myPrefixStr = *pPrefixStr;
            } else {
                myPrefixStr.clear();
            }
            ::sprintf (buffer, "%u+", myPeaces);
            myPrefixStr += buffer;
            retVal += getStaircases (peacesDown, myPeaces, &staircaseStr, &myPrefixStr);
            *pStaircaseStr += ';';
            *pStaircaseStr += staircaseStr;
            peacesDown--;
            myPeaces++;
        }
    }
    return retVal;
}

#include <stdio.h>
#include <stdlib.h>
 
int max_cub= 0;
int **ppvar= NULL;
 
void init_lesenka( int new_max_cub );
void final_lesenka( void );
int get_var( int cub, int width );
int calc_var( int cub, int width );
void print_ppvar();
 
 
/**************************************/
int main( int argc, char *argv[] ) {
 
int n, i;
 
argc--; argv++;
if ( argc != 1 ) {
    fprintf( stderr, "Usage: lesenka N\n" );
    exit( 2 );
}
n= atoi( argv[0] );
 
init_lesenka( n );
 
print_ppvar();
printf( "\n" );
 
printf( "n  " );
for ( i= 0; i<=n; i++ ) { printf( " %3d", i ); }
printf( "\n" );
 
printf( "var" );
for ( i= 0; i<=n; i++ ) { printf( " %3d", get_var( i, i ) ); }
printf( "\n" );
 
final_lesenka();
 
return 0;
 
} // main()
 
 
/**************************************/
void init_lesenka( int new_max_cub ) {
 
int i, j;
 
if ( ppvar != NULL ) { return; }
if ( new_max_cub>1 ) { max_cub= new_max_cub; } else { max_cub= 1; }
 
ppvar= (int**)malloc( (max_cub+1)*sizeof(int*) );
for ( i= 0; i<=max_cub; i++ ) {
    ppvar[i]= (int*)malloc( (max_cub+1)*sizeof(int) );
    for ( j= 0; j<=max_cub; j++ ) { ppvar[i][j]= -1; }
}
ppvar[0][0]= 1;
ppvar[1][1]= 1;
 
for ( i= 0; i<=max_cub; i++ ) {
    for ( j= 0; j<=i; j++ ) {
        calc_var( i, j );
    }
}
 
} // init_lesenka()
 
/**************************************/
void final_lesenka( void ) {
 
int i;
 
if ( ppvar == NULL ) { return; }
for ( i= 0; i<=max_cub; i++ ) {
    free( ppvar[i] );
}
free( ppvar );
ppvar= NULL;
max_cub= 0;
 
} // final_lesenka()
 
 
/**************************************/
int get_var( int cub, int width ) {
 
if ( cub<0 || cub>max_cub || width<0 ) { return -1; }
 
if ( cub<width ) { width= cub; }
return ppvar[cub][width];
 
} // get_var()
 
 
/**************************************/
int calc_var( int cub, int width ) {
 
int w, sum;
 
if ( cub<width ) { width= cub; }
if ( ppvar[cub][width] >= 0 ) { return ppvar[cub][width]; }
 
sum= 0;
for ( w= 1; w<=width; w++ ) {
    sum+= calc_var( cub-w, w-1 );
}
ppvar[cub][width]= sum;
return sum;
 
} // calc_var()
 
 
/**************************************/
void print_ppvar( void ) {
 
int i, j;
 
printf( "   " );
for ( j= 0; j<=max_cub; j++ ) { printf( " %3d", j ); }
printf( "\n" );
 
for ( i= 0; i<=max_cub; i++ ) {
    printf( "%2d:", i );
    for ( j= 0; j<=max_cub; j++ ) { printf( " %3d", ppvar[i][j] ); }
    printf( "\n" );
}
 
} // print_ppvar()