最小硬币变化问题 - 最小公倍数

Question

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

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

他建议使用面额 [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？

谢谢回答。

Answer 1

这些值的 LCM 提供了“断点”的最小上限，在该点上我们不能轻松地假设最大面额硬币是解决方案的一部分。一点数论就可以证明 LCM 是一个边界。

50 是 {25, 10} 的最小公倍数。对于任何数量 >= 50，任何至少包含 5*10 的组合都可以将该元素替换为 2*25，从而减少硬币数量。这一论点适用于所有其他硬币及其组合。这个简单的演示并不普遍适用于LCM以下；会有一些金额作为反例。

为了使整个算法易于理解和维护，我们仅使用两个阶段：断点上方最大的硬币，以及下方的完整 DP 解决方案 - 对于大多数应用程序，即使是暴力解决方案通常也足够有效以达到实际目的。