The Grandest Staircase Of Them All

Problem

With the LAMBCHOP doomsday device finished, Commander Lambda is preparing to debut on the galactic stage – but in order to make a grand entrance, Lambda needs a grand staircase! As the Commander’s personal assistant, you’ve been tasked with figuring out how to build the best staircase EVER.

Lambda has given you an overview of the types of bricks available, plus a budget. You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks). Commander Lambda wants to know how many different types of staircases can be built with each amount of bricks, so they can pick the one with the most options.

Each type of staircase should consist of 2 or more steps. No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step’s height is classified as the total amount of bricks that make up that step. For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)

#
##
21

When N = 4, you still only have 1 staircase choice:

#
#
##
31

But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:

#
#
#
##
41

#
##
##
32

Write a function called solution(n) that takes a positive integer n and returns the number of different staircases that can be built from exactly n bricks. n will always be at least 3 (so you can have a staircase at all), but no more than 200, because Commander Lambda’s not made of money!

My Solution

I have to admit that I had to cheat a bit with this problem, I knew it had something to do with dynamic programming, but I couldn’t figure it out.

After doing some googling, I found this post where they introduce Partition a number theory that indicates a solution to the problem.

The thread is very interesting, and they pretty much provide the solution in code, though not all of it.

However, a few things in the thread still remained a mistery when it came to the parts of code they provide, so I wrote the code, taking a different approach, but based on the idea, and this is what I came up with:

def solution(n):
    m = [[0 for i in range(n + 1)] for j in range(n + 1)]
    m[0][0] = 1  # base case
    for stair in range(1, n + 1):
	    for left in range(0, n + 1):
	        m[stair][left] = m[stair - 1][left]
	        if left >= stair:
	            m[stair][left] += m[stair - 1][left - stair]
	          	
    return m[n][n] -1

Juan Cruz Martinez

¡Hola!

Soy Juan Cruz Martinez, el fundador de LiveCodeStream.dev. Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé LiveCodeStream.dev porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.