Нужно решить задачу До 268
года до нашей эры в Древнем Риме было шесть основных монет:

Унция (монета номиналом 1
унция)
Секстанс (монета номиналом 2
унции)
Квадранс (монета номиналом 3
унции)
Триенс (монета номиналом 4
унции)
Семис (монета номиналом 6
унций)
Асс (монета номиналом 12
унций)
Однажды римлянин Публий взял с собой по две монеты каждого из шести номиналов (всего —
12
монет) и отправился на рынок. Сколькими способами он сможет без сдачи оплатить своими монетами покупку стоимостью 46
унций? Монеты одного номинала считайте одинаковыми.

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться методом динамического программирования. Создадим массив dp, где dp[i] будет хранить количество способов оплатить сумму i унций используя только первые j типов монет.

Изначально у нас есть только од способ оплатить сумму 0 - не использовать ни одной монеты. Таким образом, dp[0] = 1.

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

После заполнения массива dp ответом на задачу будет значение dp[46]. Таким образом, ответ на задачу - 32 способа оплатить сумму 46 унций без сдачи.