Размен монет: чем «число способов» отличается от «минимума монет» в порядке циклов?
Две задачи про размен суммы монетами заданных номиналов: (1) минимальное число монет на сумму S и (2) число способов разменять S. Код почти одинаковый, но в одном случае я считаю комбинации, а в другом — почему-то перестановки (порядок монет), и получаю неверный ответ. От чего это зависит?
2 ответа
Разница — в порядке вложенности циклов.
Для минимума монет порядок не важен (мы берём min, перестановки дают тот же набор):
vector<int> dp(S + 1, INT_MAX);
dp[0] = 0;
for (int s = 1; s <= S; s++)
for (int c : coins)
if (c <= s && dp[s - c] != INT_MAX)
dp[s] = min(dp[s], dp[s - c] + 1);
Для числа способов порядок критичен. Если внешний цикл по сумме, а внутренний по монетам — посчитаешь упорядоченные последовательности (1+2 и 2+1 как разные). Чтобы считать комбинации (наборы без учёта порядка), внешний цикл должен быть по монетам:
vector<long long> dp(S + 1, 0);
dp[0] = 1;
for (int c : coins) // монеты снаружи!
for (int s = c; s <= S; s++)
dp[s] += dp[s - c];
В способах берём long long — число способов растёт экспоненциально и легко переполняет int. Сложность обеих O(S · |coins|). Запомни: монеты во внешнем цикле → каждая монета «вводится один раз» → комбинации.
Уточнение про базу: dp[0] = 1 в задаче о числе способов означает «есть ровно один способ набрать сумму 0 — пустой набор». Это не off-by-one, а семантически верная база, без неё всё ДП будет нулевым. А в задаче минимума dp[0] = 0 (нуль монет на нулевую сумму) и остальное INF. Проверка dp[s-c] != INF перед +1 обязательна, иначе INF + 1 переполнится и сломает min.