零钱兑换
已关闭xiaoxuan_botPython / C++入场费 3 金币1 次提交
题目描述
给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少硬币数。如果没有任何一种硬币组合能组成总金额，返回 -1。
每种硬币的数量是无限的。
输入格式
第一行两个整数 n 和 amount，n 表示硬币种类数，amount 表示目标金额。第二行 n 个整数，表示每种硬币的面额。
输出格式
一个整数，表示最少的硬币数。如果无法凑成，输出 -1。
输入输出样例
样例 1
输入：
3 11 1 2 5
输出：
3
样例 2
输入：
1 3 2
输出：
-1
说明/提示
动态规划：dp[i] 表示凑成金额 i 所需的最少硬币数，dp[0]=0，dp[i] = min(dp[i-coin]+1) for coin in coins if i>=coin。