5-й раунд: 30 минут LP + вопрос по кодированию https://leetcode.com/problems/coin-change/
Вам выдаются монеты разного достоинства и общая сумма денег сумма. Напишите функцию для вычисления наименьшего количества монет, необходимого для получения этой суммы. Если эта сумма не может быть получена какой-либо комбинацией монет, верните -1
Решение: динамическое программирование
Я использовал динамическое программирование для решения этой проблемы. Итак, я представил количество монет, которое вам нужно, чтобы восполнить эту сумму, как dp [amount]. Например: согласно приведенным выше примерам dp [11] = 3 {5,5,1}, dp [10] = 2 {5,5} Но как создать этот динамический массив? Первое, что вы должны знать, это знать начальные значения динамического массива. Как правило, вы можете легко найти эти начальные значения, например: dp [0] = 0, а затем вы можете увидеть это из следующего рисунка о том, как создать динамический массив.
Сложность времени: O (n²)
Ссылка: https://leetcode.com/problems/coin-change/
