Проект Euler31: Понимание программного решения

Question

Я пытаюсь понять решение Проект Euler #31 Я нашел на форумах.

Проблема в том, что нам дают монеты со следующими значениями:

coins=[1,2,5,10,20,50,100,200]

Нам поручено генерировать все возможные способы достижения 200. Например, 10*10+100 = 200 будет одним из возможных способов.

1. Вопрос 2: Как работает код ниже! Это выглядит очень элегантно, просто и просто по сравнению с моим подходом и проходит быстрее.

Когда я просматривал форумы, я нашел это решение:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

Первая строка - это только список значений монет. Вторая строка создает массив с 1, за которым следует 200 0. Но следующие четыре строки меня смутили. Я думаю, что это увеличение количества возможных способов в массиве, поэтому case_num [200] даст последнюю запись в списке, но я понятия не имею, как это работает.

Answer 1

Как вы сказали, это очень хорошее решение. Код основан на самой итерации 1-200 с каждой деноминацией монеты.

Массив case_num изначально состоит из [1, 0, 0, 0, 0, 0 ... 0, 0, 0

Что эти числа (кроме исходного 1) означают, сколько способов вы можете создать до заданного общего (представленного индексом числа), используя монеты в p_list, с которыми вы итерации до сих пор.

Первая монета в p_list - 1. Так что, если 1 может поместиться в индекс, вы принимаете значение в предыдущем индексе и добавляете его в свой текущий индекс. Это работает, потому что, если есть 5 известных способов добраться до 25, и вы только что нашли монеты размера 1, то также будет 5 способов добраться до 26. [Каждый из предыдущих 5 способов добраться до 25] + 1 монета Анкет

Таким образом, после итерации с 1 -го вы получите [1, 1, 1, 1, 1 ... 1, 1

Теперь вы двигаетесь в монетах. На этот раз вы используете монету 2. Давайте пройдемся через процесс 1 еще. Если 2 меньше, то индекс, то вы добавляете количество способов добраться до предыдущего индекса к вашему текущему индексу.

Например, 2 не вписывается в индекс 1, но вписывается в индекс 2. Так что вы только что создали новый способ добраться до 2 из 0, поэтому вы берете все способы, которыми вы можете добраться до 0 и добавить их в свой текущий индекс. В индексе 27, 2 вписывается в индекс, поэтому вы берете количество способов добраться до 25 и добавить их в 27, потому что теперь у вас есть (все эти способы добраться до 25 + одна монета) + (все способы Вы должны были добраться до 27, прежде чем вы узнали, что у вас есть монеты размера 2).

Таким образом, после итерации с 2 -х вы получите [1, 1, 2, 2, 3, 3, 4, 4 ...

Если у вас все еще возникают проблемы, это может быть того, чтобы попытаться пройти всю программу (возможно, на уменьшенном общем случае, как 50 вместо 200).