#include <stdio.h>

void main()
{
    int N,i,j;
    scanf("%d",&N);
    double **F=new double*[N];
    for(i=0;i<N;i++)
     {
        F[i]=new double[N];
        for(j=0;j<N;j++) F[i][j]=0;
        F[i][i]=1;
    }
    for(i=1;i<N;i++)
        for(j=i-1;j>=0;j--)  F[i][j]=F[i-j-1][j+1]+F[i][j+1];
    printf("%.0lf",F[N-1][0]-1);
}

Can you explain what do elements of your matrix keep?

Can u explain, or give where I can read about this task?

Let's designate height of a step i for ai then we need to find all such sets
0 <a1 <a2 <... <ai and a1+a2 +... +ai=N. That is it is necessary to count quantity of splittings of number N on decreasing composed. F[i][j] is a quantity of splittings of number i on composed not less j. Then the formula is fair
 F[i][j] =F[i-j][j+1] + F[i][j+1]
F[i-j][j+1] - the number j participates in splitting
F[i][j+1] - does not participate

P.S.
Sorry for my English

Edited by author 19.09.2008 11:04