Ссылка: https://leetcode.com/problems/coin-change/
Первая мысль
Мы можем подумать, что если каждый раз брать самую большую монету, нам может понадобиться наименьшее количество монет, но на самом деле это не так, потому что существует вероятность того, что монеты не могут составить сумму. Здесь нам нужно использовать динамическое программирование, мы генерируем массив с длиной нужной нам суммы. Начиная с нуля, выполните поиск по всей стоимости монет, чтобы увидеть, достигли ли мы какой-либо суммы раньше, чтобы мы могли добавить еще одну монету, чтобы получить текущую сумму. Число в массиве означает минимальное количество монет, необходимое для достижения текущей суммы. Таким образом, мы можем просто вернуть последний элемент массива.
