2
\$\begingroup\$

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?

\$\endgroup\$
  • 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 '15 at 1:57
  • \$\begingroup\$ Ah, sorry, I misunderstood the purpose of this site \$\endgroup\$ – shane Aug 21 '15 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\$ – Level River St Aug 21 '15 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\$ – Peter Taylor Aug 21 '15 at 15:01