给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。
例如,美国硬币面额有1、5、10、25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。
对于每一种面额,我们都分别计算所需要的硬币数量。具体算法如下:
如果全部用1美分的硬币,一共需要36个硬币
如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
如果用10美分的硬币,则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个