题目描述
Example 1:
Example 2:
解题思路
本题给出了硬币的面值，要求用最少的硬币组成一个数，组不成就返回-1.
首先声明一个大小为amount+1的数组fewestCoins，fewestCoins[i]表示组成数字i所需的最少硬币数，组不成则为-1，最后fewestCoins[amount]即为所求。将数组的第一个元素初始化为0，因为使用0个硬币就能组成0这个数，其余元素初始化为最大正整数。状态转移为fewestCoins[i] = min(fewestCoins[i], fewestCoins[i - coins[j]] + 1),其中coins[j]为硬币面值，若没有更新fewestCoins[j]，则将其置为-1。