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.

It makes sense to just add P(1) + ... + P(n), but how to find all possible pyramids with 1 < i <= n bricks?

Code length is not as important as the solution itself, but go ahead and have fun with it?

  • 2
    \$\begingroup\$ You need to know the answer to a question to pose it as a challenge. Otherwise, you don't know if it will be interesting to optimize. Really, it sounds like you want programming help, and there's sites for that. Also, it's totally unclear what the bricks are and how they are stacked. \$\endgroup\$
    – xnor
    Aug 21, 2015 at 1:57
  • \$\begingroup\$ Ah, sorry, I misunderstood the purpose of this site \$\endgroup\$
    – shane
    Aug 21, 2015 at 1:59
  • 1
    \$\begingroup\$ I would say with quite a bit of work there's a valid challenge in there somewhere. Specifically: 1. proper specification of what brick stackings are valid, with examples (is a flat row a valid "pyramid") 2. definition of winning criterion (for example code golf = shortest code.) \$\endgroup\$ Aug 21, 2015 at 5:04
  • \$\begingroup\$ The number of pyramids with i bricks is A000009(i). From a quick look at the formula section in OEIS, I would vote to close a question which asks us to calculate it as a duplicate of this related question. \$\endgroup\$ Aug 21, 2015 at 15:01