How to solve this problem in o(n^2)?

Let's start from the beginning:
Let R(n) will be the function that returns count of unique staircases.
Now let's introduce function G(n,j) that returns count of unique staircases each first step of which has more than j bricks.
Then R(n) = G(n,0) - 1 . We have to subtract one because it is the case when all bricks are spent on the first step.

G(n,j) = (n>j ? 1 : 0) + (G(n-j-1, j+1) + G(n-j-2, j+2) + ... +G(0,n))

G(n,j-1) - G(n,j) = (n == j ? 1 : 0) + G(n-j, j) => G(n,j) = G(n,j-1) - G(n-j,j) - (n == j ? 1 : 0)

We know that in the case when n<=j G(n,j) = 0, so we can solve upper equation only for cases when j<n, in such cases upper formula will transform to G(n,j) = G(n,j-1) - G(n-j,j).

But we still have to solve the cases when j == 0 and i > j as G(n, 0) = 1 + G(n-1, 1) + G(n-2, 2) + ... + G(0,n)

//Alloc and init matrix g with zeroes

//Calculat g matrix
for(i = 2; i<=N; ++i){
    g[i][0] = 1;
    for(j=1; j<i;++j){
        g[i][0] += g[i-j, j];
    }
    for(j=1; j<i;++j){
        g[i][j] = g[i][j-1] - g[i-j,j];
    }
}
cout<<g[N][0]-1;

Edited by author 09.02.2020 17:14