Finding all possible designs for a staircase I was given this problem as an extra credit challenge, but was completely stumped on how to even approach it. The problem: > You have 50 blocks to build a staircase, how many different designs are possible? > > **Staircase Rules:** > > 1: A staircase must have at least two steps > > 2: A step must be at least one block shorter than the one before it > > 3: All bricks must be used in the design How would you start making a formula to solve this?

The way to solve this with dynamic programming is pretty simple. For a positive integer $k$, let $B_k(n)$ be the number of partitions into elements of distinct size of $n$, such that every summand is among $1,2,\dots, k$. Clearly we want $B_{49}(50)$.

Then clearly $B_{k+1}(n)=B_{k}(n-k-1)+B_k(n)$.

Using this we can fill an array of size $51$ with $B_1(n)$ for all $0\leq n\leq 50$ and actualize it from $B_k$ to $B_{k+1}$ until we get $B_{50}(n)$, which is what we need. Here is come c++ code:


#include

int B[51]; // this array saves the results

int main(){
B[0]=1;
for(int i=1;i<50;i++){ // here we actualize from B_(i-1) to B_i
for(int j=50;j>=i;j--){ // we let B_i(j)=B_(i-1)(j-i)+B_(i-1)(j)
B[j]+=B[j-i];
}
}
printf("%d\
",B[50]); // we print the result
}


Output:

$3657$