find all possible arrangements of bricks with P sections

Question

We are given N rectangular bricks. All bricks are of equal width and have a unique number i where 0 < i < N+1. The ith brick has height of i centimeters. We have to arrange all bricks in a sequence and depending on the sequence several succeeding bricks form a sequence of decreasing height. We denote such a sequence as section. Sections can consist of only one brick.
For instance, the brick sequence 1 3 4 2 has three sections: (1), (3), (4,2).
Now, given two parameters N and P we have to find all possible arrangements of N bricks that form P sections. I am trying to find a bottom-up DP approach but struggle to find the right recursive dependency formula. Help is greatly appreciated!

Edit Edit: This is my implementation:

#include <iostream>
using namespace std;

void solve(int solutions[], int sections[], int i, int P){
    if (i == 0){
        solutions[i] = 1;
        return;
    }
    solutions[i] = solutions[i-1]*P + (sections[P-2]-P+1);
    for (int j = min(i,P); j >= 0; j--){
        if (j == 0){
            sections[j] = 1;
        }
        else {
            sections[j] = sections[j]*(j+1) + (sections[j-1] - j+1);
        }
    }
}

int main(){
    int N,P;
    cin >> N >> P;
    while (N != 0){
        int solutions[N] = {};
        int sections[P] = {};
        for (int i = 0; i < N; i++){
            solve(solutions,sections,i,P);
        }
        cout << (solutions[N-1]) << endl;
        cin >> N >> P;
    }
    return 0;
}
```

Answer 1

I'll call an arrangement of $n$ bricks that consists of $p$ decreasing sections an $(n,p)$ arrangement.

Suppose you have one such $(n,p)$ arrangement, and that you are going to add one brick of size $n+1$. There are $n+1$ places that the brick can be inserted. If it is put at the left end of one of the $p$ existing sections, then you will still have $p$ sections. However, if it is put anywhere else then a new section will be created (either by splitting an existing section or if you put it at the right hand side the new brick forms a new section on its own). There are $n+1-p$ ways for this to happen.

So from every $(n,p)$ you generate $p$ new $(n+1,p)$ arrangements and $n+1-p$ new $(n+1,p+1)$ arrangements.

This is sufficient to create a program to forward fill a two-dimensional array starting from the single $(1,1)$ arrangement. You will have to use a two-dimensional array, as you have to index along both the $n$ and $p$ variables. I do not think it can be done with a one-dimensional array directly.

Note that of course you don't actually need the full array in memory, as you only really need two rows at any one time - row $n$ that that was previously calculated and row $n+1$ that you are generating from it. So programmatically you can do it with two 1-dimensional arrays.