Pyramids dynamic programming

Question

I encountered this question in an interview and could not figure it out. I believe it has a dynamic programming solution but it eludes me.

Given a number of bricks, output the total number of 2d pyramids possible, where a pyramid is defined as any structure where a row of bricks has strictly less bricks than the row below it. You do not have to use all the bricks.

A brick is simply a square, the number of bricks in a row is the only important bit of information.

Really stuck with this one, I thought it would be easy to solve each problem 1...n iteratively and sum. But coming up with the number of pyramids possible with exactly i bricks is evading me.

example, n = 6

X

XX

X
XX   XXX

X
XXX   XXXX

XX      X
XXX   XXXX   XXXXX

X
XX      XX       X
XXX   XXXX   XXXXX   XXXXXX

So the answer is 13 possible pyramids from 6 bricks.

edit

I am positive this is a dynamic programming problem, because it makes sense to (once you've determined the first row) simply look to the index in your memorized array of your remainder of bricks to see how many pyramids fit atop.

It also makes sense to consider bottom rows of width at least n/2 because we can't have more bricks atop than on the bottom row EXCEPT and this is where I lose it and my mind falls apart, in certain (few cases) you can I.e. N = 10

X
XX
XXX
XXXX

Now the bottom row has 4 but there are 6 left to place on top

But with n = 11 we cannot have a bottom row with less than n/2 bricks. There is another wierd inconsistency like that with n = 4 where we cannot have a bottom row of n/2 = 2 bricks.

Answer 1

Let's choose a suitable definition:

f(n, m) = # pyramids out of n bricks with base of size < m

The answer you are looking for now is (given that N is your input number of bricks):

f(N, N+1) - 1

Let's break that down:

• The first N is obvious: that's your number of bricks.
• Your bottom row will contain at most N bricks (because that's all you have), so N+1 is a sufficient lower bound.
• Finally, the - 1 is there because technically the empty pyramid is also a pyramid (and will thus be counted) but you exclude that from your solutions.

---

The base cases are simple:

f(n, 0) = 1   for any n >= 0
f(0, m) = 1   for any m >= 0

In both cases, it's the empty pyramid that we are counting here.

---

Now, all we need still is a recursive formula for the general case.

Let's assume we are given n and m and choose to have i bricks on the bottom layer. What can we place on top of this layer? A smaller pyramid, for which we have n - i bricks left and whose base has size < i. This is exactly f(n - i, i).

What is the range for i? We can choose an empty row so i >= 0. Obviously, i <= n because we have only n bricks. But also, i <= m - 1, by definition of m.

This leads to the recursive expression:

f(n, m) = sum f(n - i, i) for 0 <= i <= min(n, m - 1)

---

You can compute f recursively, but using dynamic programming it will be faster of course. Storing the results matrix is straightforward though, so I leave that up to you.

---

Coming back to the original claim that f(N, N+1)-1 is the answer you are looking for, it doesn't really matter which value to choose for m as long as it is > N. Based on the recursive formula it's easy to show that f(N, N + 1) = f(N, N + k) for every k >= 1:

f(N, N + k) = sum f(N - i, i) for 0 <= i <= min(N, N + k - 1)
            = sum f(N - i, i) for 0 <= i <= N
            = sum f(N - i, i) for 0 <= i <= min(N, N + 1 - 1)

Answer 2

In how many ways can you build a pyramid of width n? By putting any pyramid of width n-1 or less anywhere atop the layer of n bricks. So if p(n) is the number of pyramids of width n, then p(n) = sum [m=1 to n-1] (p(m) * c(n, m)), where c(n, m) is the number of ways you can place a layer of width m atop a layer of width n (I trust that you can work that one out yourself).

This, however, doesn't place a limitation on the number of bricks. Generally, in DP, any resource limitation must be modeled as a separate dimension. So your problem is now p(n, b): "How many pyramids can you build of width n with a total of b bricks"? In the recursive formula, for each possible way of building a smaller pyramid atop your current one, you need to refer to the correct amount of remaining bricks. I leave it as a challenge for you to work out the recursive formula; let me know if you need any hints.

Answer 3

You can think of your recursion as: given x bricks left where you used n bricks on last row, how many pyramids can you build. Now you can fill up rows from either top to bottom row or bottom to top row. I will explain the former case.
Here the recursion might look something like this (left is number of bricks left and last is number of bricks used on last row)

f(left,last)=sum (1+f(left-i,i)) for i in range [last+1,left] inclusive.

Since when you use i bricks on current row you will have left-i bricks left and i will be number of bricks used on this row.

Code:

int calc(int left, int last) {
    int total=0;
    if(left<=0) return 0;  // terminal case, no pyramid with no brick
    for(int i=last+1; i<=left; i++) {
        total+=1+calc(left-i,i);
    }
    return total;
}

I will leave it to you to implement memoized or bottom-up dp version. Also you may want to start from bottom row and fill up upper rows in pyramid.