凑零钱问题-动态规划、回溯、贪心

题目：给你k种面值的硬币，面值分别为c1,c2 … ck，每种硬币的数量⽆限，再给⼀个总金额amount，问你最少需要⼏枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
**一、动态规划：**暴力递归，记忆型递归，迭代法
状态就是当前还有余额amount
状态转移方程为：

状态amount所需要的硬币数就是状态amount-k(结果必须大于等于0)所需要的硬币数+1，其中k是面值。
三种方法的代码见找零钱动态规划代码.
二、回溯
决策树

代码链接: 回溯法解决找零钱问题.
回溯法能够找出所有的硬币组合，从中挑选硬币数最少者就行了
三、贪心算法
贪心规则：选择小于等于当前余额的最大面值
代码链接：贪心法解决找零钱问题.
贪心法一般找不到最优解，但找零钱问题确实是最优的。并且可以给出最优解的构成