Размен монетами: почему порядок вложенных циклов меняет ответ
Считаем, сколькими способами набрать сумму 5 монетами номиналов 1, 2 и 5 (монет каждого номинала неограниченно).
coins = [1, 2, 5]
target = 5
dp = [0] * (target + 1)
dp[0] = 1
for c in coins:
for s in range(c, target + 1):
dp[s] += dp[s - c]
print(dp[target])
Что напечатает код и что изменится, если поменять циклы местами (внешний по суммам, внутренний по монетам)?
- Напечатает 4; перестановка циклов ничего не изменит, ведь сложение коммутативно
- Напечатает 9; внешний цикл по монетам как раз считает упорядоченные последовательности
- Напечатает 4; после перестановки получится 9 — это уже упорядоченные последовательности
- Напечатает 4; после перестановки останется 4, изменится только порядок обновления массива dp