给定不同面额的硬币 coins 和一个总金额 amount.编写一个函数来计算可以凑成总金额所需的最少的硬币个数.如果没有任何一种硬币组合能组成总金额,返回 -1.
你可以认为每种硬币的数量是无限的.
拿到这种题型,感觉就是动态规划.动态规划问题的一般形式就是求最值,求最值就是穷举所有的可能性.
动态规划穷举主要是存在重复子问题,而且还具备最优的子结构,这样才能有最值.最重要的还有状态转移方程,能写出来就完成了大部分了.
就这道题而言,肯定是重复子问题:拿硬币,也是具备最优的子结构:让每种类似的硬币数量最小,然后就是考虑状态转移方程了.