Ежедневная проблема кодирования 316: проблема смены монет - определение достоинства?

Question

У меня проблемы с ежедневным кодированием, и я застрял в одной из проблем. Это выглядит так:

Вам дан массив длины N, где каждый элемент i представляет количество способов, которыми мы можем произвести i единиц изменения. Например, [1, 0, 1, 1, 2] будет указывать, что существует только один способ сделать 0, 2 или 3 единицы, и два способа сделать 4 единицы.

При наличии такого массива Определите наименования, которые должны быть использованы. В приведенном выше примере, например, должны быть монеты со значениями 2, 3 и 4.

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

Кто-то уже решил эту проблему здесь , но она лишена каких-либо объяснений.

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

Заранее спасибо!

Answer 1

Если вы решаете проблему смены монет, лучшим способом является использование множества способов внесения изменений с частичным набором доступных номиналов и добавление нового номинала d путем обновления массива следующим образом. :

for i = d upto N
    a[i] += a[i-d]

Ваша реальная проблема заключается в обратном: поиск деноминаций на основе общего количества способов. Обратите внимание, что если вы знаете один d, вы можете удалить его из массива way, выполнив в обратном порядке описанную выше процедуру:

for i = N downto d
    a[i] -= a[i-d]

. Вы можете найти наименьший доступный номинал, найдя первые 1 в массиве ( кроме значения по индексу 0, который всегда равен 1). Затем, как только вы найдете наименьший номинал, вы можете убрать его влияние на массив путей и повторять до тех пор, пока массив не обнулится (кроме первого значения).

Вот полное решение в Python :

def rways(A):
    dens = []
    for i in range(1, len(A)):
        if not A[i]: continue
        dens.append(i)
        for j in range(len(A)-1, i-1, -1):
            A[j] -= A[j-i]
    return dens

print(rways([1, 0, 1, 1, 2]))

Возможно, вы захотите добавить проверку ошибок: если вы найдете ненулевое значение, отличное от 1, при поиске следующего наименования, то исходный массив недопустим.

Для справки и сравнения приведем код для вычисления способов внесения изменений из набора наименований:

def ways(dens, N):
    A = [1] + [0] * N
    for d in dens:
        for i in range(d, N+1):
            A[i] += A[i-d]
    return A

print(ways([2, 3, 4], 4))