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?


closed as off-topic by xnor, Jwosty, FryAmTheEggman, samgak, Alex A. Aug 21 '15 at 2:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This site is for programming contests and challenges. General programming questions are off-topic here. You may be able to get help on Stack Overflow." – xnor, Jwosty, FryAmTheEggman, samgak, Alex A.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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