ЯсноПонятно24

Для решения этой задачи можно воспользоваться методом динамического программирования.

Пусть dp[i][j] - количество способов набрать сумму j, используя только монеты с достоинством до i.

Изначально заполним массив dp[i][j] нулями, кроме dp[0][0] = 1.

Затем пройдем по всем монетам и для каждой монеты обновим значения dp[i][j] следующим образом: dp[i][j] = dp[i][j] + dp[i-1][j-k*coin[i]], где k - количество монет i, которые мы используем.

После обновления всех значений массива dp, ответом на задачу будет dp[4][94], так как у нас четыре типа монет и нам нужно набрать сумму 94.

Программный код на Python:

coins = [1, 2, 5, 10]
n = 94
dp = [[0] * (n + 1) for _ in range(len(coins))]
dp[0][0] = 1

for i in range(len(coins)):
    for j in range(n + 1):
        for k in range(7):
            if j - k * coins[i] < 0:
                break
            dp[i][j] += dp[i - 1][j - k * coins[i]]

print(dp[-1][-1])

Ответ: 6.