CP38 · 零钱兑换

中等动态规划背包时限 1000 ms(参考)
题目描述

给定 n 种面额的硬币(每种数量无限)和总金额 amount,求凑成 amount 所需的最少硬币个数;无法凑成输出 -1。

输入描述

第一行两个整数 n、amount(1 ≤ n ≤ 20,0 ≤ amount ≤ 10^4);第二行 n 个正整数面额。

输出描述

一行,一个整数:最少硬币数或 -1。