Coin change - the number of ways - Алгоритмы и структуры данных

Дана система монет, состоящая из n монет, каждая из которых имеет положительную стоимость . Необходимо найти количество способов получить итоговую сумму x, используя эти монеты.

Например, если стоимости монет и мы хотим получить сумму 5, существует 4 различных способа сделать это: 5, 1 + 2 + 2, 1 + 1 + 1 + 2 и 1 + 1 + 1 + 1 + 1. В отличие от combination sum, здесь порядок не важен, — нас интересует только набор (multiset) используемых монет.

Ввод

Первая строка содержит два целых числа n (1 ≤ n ≤ 100) и x (1 ≤ x ≤ ).

Следующая строка содержит n целых чисел, разделённых пробелами: (1 ≤ ≤ ).

Вывод

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

Примеры

Ввод	Вывод
3 5 1 2 5	4
3 9 2 3 5	3

Пояснение

5, 1 + 2 + 2, 1 + 1 + 1 + 2, 1 + 1 + 1 + 1 + 1

3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3

Tutorial

Заметим, что если мы будем хранить состояние d[s], где d[s] означает число различных способов получить сумму s с использованием всех монет, то столкнёмся с проблемой повторного подсчёта одних и тех же комбинаций монет в разных порядках. Например, набор 1 + 2 + 2 будет учтён несколько раз как разные перестановки (хотя по условию порядок не важен).

Чтобы избежать этой проблемы, мы будем считать, сколько способов получить значение s, перебирая монеты до некоторого ci (это индекс монеты в массиве c). Мы можем вообще не использовать монету ci или использовать её несколько раз — всё это отражается в состоянии. Таким образом, состояние d[s][ci] будет обозначать количество способов получить сумму s, учитывая все монеты до ci.

Существует два перехода, позволяющих попасть из предыдущих состояний к текущему d[s][ci] (где индекс текущей монеты — ci, а её значение — val):

Мы можем не использовать монету ci → d[s][ci - 1]

Мы можем использовать монету ci 0, 1, 2, … k раз → d[s - val][ci]

Суммарно количество способов получить сумму s с учётом всех монет до ci будет равно сумме соответствующих предыдущих состояний.

c = [...]
x = ...
# Инициализируем d, создавая (x+1) строк и len(c) столбцов, заполненных нулями
d = [[0] * len(c) for _ in range(x + 1)]

Сначала мы обрабатываем первую монету и обновляем состояние d[s][0] для всех возможных сумм s с использованием этой первой монеты. Затем переходим ко второй монете и обновляем все состояния d[s][1], потом — к третьей и так далее, пока не рассмотрим последнюю монету.

После обработки всех монет мы можем вывести итоговое количество способов для суммы x, посмотрев на состояние после рассмотрения последней монеты: d[x][len(c) - 1]:

for ci, val in enumerate(c):      # Перебираем монеты по одной
    d[0][ci] = 1                  # Можно получить сумму 0 без использования монет
    for s in range(1, x + 1):     # Перебираем все суммы от 1 до x включительно
        if ci - 1 >= 0:           # (1) Не использовать текущую монету ci
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) Использовать монету ci 0 или более раз
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])

😎 Можно ли хранить массив d в одиномерном виде?

Мы обрабатываем монеты по одной, поэтому все вычисленные состояния для монеты ci - 2 и более ранних нам уже не нужны. На каждой итерации нас интересуют только текущая монета ci и предыдущая ci - 1. Значит, мы можем держать состояние для предыдущей монеты в одном массиве, а текущее состояние — в другом.

😎 А можно обойтись без дополнительного массива и хранить только одномерный d?

Если приглядеться, единственное, что нужно от состояния предыдущей монеты, — это прибавление prev[s] к d[s]. Следовательно, мы можем даже не хранить предыдущий массив, а обойтись одним:

# Инициализируем d из x+1 элемента
d = [1] + [0] * x                 # Можно получить сумму 0 без использования монет

for ci, val in enumerate(c):      # Перебираем монеты по одной
    for s in range(1, x + 1):     # Перебираем все суммы от 1 до x включительно
        if s - val >= 0:          # (2) Использовать монету ci 0 или более раз
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])

Coin change - the number of ways

Ввод

Вывод

Примеры

Пояснение

Tutorial

Constraints

To check your solution you need to sign in

Sign in to continue