In order to work on my python skills, I am sometimes doing various challenges on the internet (eg on hackerrank). Googling for something else, I found this problem, and the accompanying solution on the internet, and it caught my attention:

The Grandest Staircase Of Them All

With her LAMBCHOP doomsday device finished, Commander Lambda is preparing for her debut on the galactic stage - but in order to make a grand entrance, she needs a grand staircase! As her 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 she 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 answer(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!

https://en.wikipedia.org/wiki/Partition_(number_theory)

def answer(n):# make n+1 coefficientscoefficients = [1]+[0]* n#go through all the combosfor i in range(1, n+1):#start from the back and go down until you reach the middlefor j in range(n, i-1, -1):print "add", coefficients[j-i], "to position", jcoefficients[j] += coefficients[j-i]print coefficientsreturn coefficients[n] - 1

Now I tried to understand the above solution, by walking manually through an example. For example, for

answer(10)

the options are:

1 2 3 4
1 2 7
1 3 6
1 9
1 4 5
2 3 5
2 8
3 7
4 6

So there are nine options total, that add up to 10. When I run the program, the final few lists are:

        add 1 to position 10[1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 9]add 1 to position 9[1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 9]add 1 to position 10[1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10]9

So the result is correct, but I don't understand what the final list, or all lists, have to do with the solution. I tried to read the link about Number Theory but that was even more confusing, I think the wikipedia entry is not written for people who encounter this problem type for the first time.

Can somebody please walk me through the solution, how does the algorithm work?

Regarding the answer function you posted:

At the end of each iteration of the outer loop, coefficients[x] is the number of staircases you can make with height at most i, having used a total of x blocks. (including staircases with only one stair or zero stairs).

coefficients is initialized to [1,0,0...] before the loop, indicating that there is only one staircase you can make with height at most 0. It is the one with no stairs, so you will have consumed 0 blocks to make it.

In each iteration of the loop, the coefficients array is transformed from representing max height i-1 to representing max height i, by incorporating the possibility of adding a step of height i to any shorter staircase that leaves you with at least i blocks.

finally it returns the number of ways you can get to the end after having used all n blocks, minus one since the single stair of height n is invalid.

This algorithm is an example of "dynamic programming".