algorithm - 最小硬币找零问题

该视频介绍了最小硬币的实现以进行更改。

我不清楚的地方是面试官从这里开始进入优化细节的地方。

他建议，要使用面额 [25, 10, 1] 制作硬币的最小数量，我们只需要使用算法对 50 美分以上的数字进行找零，之后我们可以安全地使用 25 美分。因此，如果数字是 100.10 美元，我们可以使用 25 美分，直到达到 50 美分，此时我们需要使用算法来计算精确值。

这对于给出 [25, 10, 1] 的面额列表是有意义的。为了获得断点数字，他建议使用面额的 LCM，在这种情况下为 50。

For example 
32 - 25 * 1 + 1 * 7 = 8 coins. But with 10 cents we can do 
32 - 10 * 3 + 1 * 2 = 5 coins.

所以我们不能仅仅假设 25 美分将包含在最小硬币数量计算中。

这是我的问题——

假设我们有面额 [25, 10, 5, 1]，lcm 仍然是 50。但是对于任何超过 25 美分的数字都没有不包括 25 的最小解。

例如 -

32 - 25 * 1 + 5 * 1 + 1 * 2 = 4 coins. 
32 - 10 * 3 + 1 * 2 = 5 coins

那么在这种情况下，断点不应该是 25 美分吗？而不是lcm？

谢谢回答。

标签： algorithm

algorithm - 最小硬币找零问题 - 最小公倍数