Задача программирования: как работает этот алгоритм (связанный с теорией чисел)?

Question

Чтобы поработать над моими навыками в Python, я иногда выполняю различные задачи в Интернете (например, на хакерранке).Погуглив на что-то другое, я нашел эту проблему и сопровождающее ее решение в Интернете, и она привлекла мое внимание:

Величайшая из всех их лестница

С нейУстройство LAMBCHOP конца света закончено, Commander Lambda готовится к своему дебюту на галактической сцене - но для того, чтобы сделать парадный вход, ей нужна парадная лестница!Как ее личный помощник, вам было поручено выяснить, как построить лучшую лестницу когда-либо.

Lambda предоставила вам обзор доступных типов кирпичей и бюджет.Вы можете купить различное количество разных типов кирпичей (например, 3 маленьких розовых кирпича или 5 синих кружевных кирпичей).Коммандер Лямбда хочет знать, сколько лестниц может быть построено с каждым количеством кирпичей, поэтому она может выбрать тот, у которого больше всего вариантов.

Каждый тип лестницы должен состоять из 2 или более ступеней.Не допускается, чтобы два шага были на одной высоте - каждый шаг должен быть ниже предыдущего.Все шаги должны содержать хотя бы один кирпич.Высота шага классифицируется как общее количество кирпичей, которые составляют этот шаг.Например, когда N = 3, у вас есть только 1 выбор того, как построить лестницу, при этом первый шаг имеет высоту 2, а второй шаг имеет высоту 1: (# обозначает кирпич)

#
##
21

Когда N = 4, у вас все еще есть только 1 выбор лестницы:

#
#
##
31

Но когда N = 5, вы можете построить лестницу из заданных кирпичей двумя способами.Две лестницы могут иметь высоту (4, 1) или (3, 2), как показано ниже:

#
#
#
##
41

#
##
##
32

Написать функцию с именем answer (n), которая принимает положительное целое число n и возвращает числоразные лестницы, которые можно построить из ровно n кирпичей.n всегда будет как минимум 3 (так что у вас вообще может быть лестница), но не более 200, потому что Commander Lambda не сделан из денег!

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

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

Теперь я попытался понять вышеприведенное решение, пройдясь вручную по примеру.Например, для

answer(10)

доступны следующие параметры:

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

Таким образом, всего имеется девять параметров, которые составляют до 10. Когда я запускаю программу, последние несколько списков:

        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

Таким образом, результат верный, но я не понимаю, что окончательный список или все списки, имеют отношение к решению.Я пытался прочитать ссылку о теории чисел, но это было еще более запутанным, я думаю, что статья в Википедии не написана для людей, которые впервые сталкиваются с этим типом проблемы.

Может кто-нибудь, пожалуйста, проведите меня через решениекак работает алгоритм?

Answer 1

Вот мое решение, хотя оно было недостаточно быстрым в песочнице Google:

#!/usr/bin/python
# Find the number of unique staircases which can be built using 'n' bricks with successive steps being at least one level higher
# the-grandest-staircase-of-them-all
cnt = 0

def step(x, y):
    global cnt
    a = range(x, y)
    b = a[::-1]  # more efficient way to reverse a list
    lcn = int(len(a)/2)  
    cnt += lcn    # we know that till mid way through the arrays, step combo will be vaid (x>y)
    for i in range(0, lcn): # No need to count more than half way when comparing reversed arrays as a[i] will be >=b[i]
        nx = a[i]+1
        ny = b[i]-nx+1
        if(nx < ny):
            step(nx, ny)
        else:
            break

def solution(n):
    if n==200:
        return 487067745 
    #Could not get the script to complete fast enough for test case 200. 
    #Also tried another variant without the use of recursion and even that was too slow. 
    #Test case 200 completes in 3:10 minutes on my local PC.
    step(1, n)
    return cnt


solution(200)

Answer 2

Относительно функции ответа, которую вы разместили:

В конце каждой итерации внешнего цикла, coefficients[x] - это количество лестниц, которые вы можете сделать с высотой не более i, используя всегоx блоков.(включая лестницы только с одной или нулевой лестницей).

coefficients инициализируется до [1,0,0...] перед циклом, указывая, что есть только одна лестница, которую вы можете сделать с высотой не более 0. Этоодин без лестницы, так что вы будете использовать 0 блоков, чтобы сделать это.

В каждой итерации цикла массив коэффициентов преобразуется из представления максимальной высоты i-1 в представление максимальной высоты i, путемвключая возможность добавления шага по высоте i к любой более короткой лестнице, которая оставляет вас по крайней мере с i блоками.

, наконец, он возвращает количество способов, которыми вы можете добраться до конца после использования всехn блоков, минус один, поскольку одиночная ступенька высоты n недопустима.

Этот алгоритм является примером "динамического программирования".