Coin Change

У тебя есть неограниченный запас монет нескольких номиналов, и ты хочешь заплатить точную сумму, используя как можно меньше монет.

Кажется, что нужно брать самую крупную монету, которая подходит, но это может не сработать. Если есть монеты [1, 3, 4] и сумма 6, то выбор самой крупной монеты сначала даст 4 + 1 + 1 — три монеты, тогда как для 3 + 3 нужны всего две.

Надёжнее постепенно строить ответ, начиная с небольших сумм. Пусть fewest[t] — наименьшее количество монет, в сумме дающих t. Чтобы заплатить 0, монеты не нужны. Для любого другого t последняя использованная монета имеет некоторое значение c, а до её добавления оставалось t - c, поэтому

fewest[t] = 1 + the smallest fewest[t - c] среди всех монет c, номинал которых не превышает t.

Для [1, 3, 4]: fewest[3] = 1, а fewest[6] = 1 + fewest[3] = 2. Если ни одна монета не приводит к сумме, которую можно набрать, то сумму t вообще нельзя заплатить.

Напиши функцию с именем coinChange, которая получает coins — список различных номиналов монет — и целое число amount, а возвращает наименьшее количество монет, сумма которых в точности равна amount. Каждый номинал монеты можно использовать сколько угодно раз. Верни -1, если нужную сумму составить невозможно, и 0, если amount равен 0.

Например, для coins = [2, 5, 10] и amount = 27 функция возвращает 4 (10 + 10 + 5 + 2), а для coins = [4, 6] и amount = 7 возвращает -1.

Ограничения: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, все значения различны, 0 <= amount <= 10^4.