问题描述
有n种硬币，面值分别为 V1,V2,…,Vn。每种都有无限多。给定非负整数S，问可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值
贪心算法
贪心算法的解不一定是最优解
但是贪心算法的解有用途，可以作为DFS的剪枝条件,搜索过程中解大于贪心算法的解时break
参考DFS实现
动态规划
公式
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
动态规划实现
DFS
当 amount==0amount==0 时剪枝，因为大面值硬币需要更多小面值硬币替换，继续减少一枚或几枚大硬币搜索出来的答案【如果有】肯定不会更优。
当 amount!=0，但已经使用的硬币数 cnt 满足了 cnt+1>=ans 时剪枝，因 amount 不为 0，至少还要使用 1 枚硬币，则继续搜索得到的答案不会更优。是 break 不是 continue，因为少用几枚面值大的硬币搜索出的方案【如果有】肯定需要更多枚面值小的硬币来替换掉这枚大的硬币【同剪枝 1 理由】，而使用这几枚大的硬币都搜索不到更好的解，故应该是 break。
使用贪心算法先算出一个解，作为剪枝条件
DFS实现