Discussion @ 1017. Staircases @ Timus Online Judge

MSDN Very easy dp problem! AC code [3] // Problem 1017. Staircases 2 Feb 2008 22:06

#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);
}

Grigor Gevorgian Re: Very easy dp problem! AC code [2] // Problem 1017. Staircases 22 Jun 2008 00:21

Can you explain what do elements of your matrix keep?

Alexander Sokolov [MAI-7] Re: Very easy dp problem! AC code [1] // Problem 1017. Staircases 20 Aug 2008 05:15

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

MSDN Re: Very easy dp problem! AC code // Problem 1017. Staircases 19 Sep 2008 11:03

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

Discussion of Problem 1017. Staircases