java - 为什么面额数组的排序在硬币兑换中很重要

Question

请在下面的链接中查看最小硬币变化问题的解决方案

http://techieme.in/minimum-number-of-coins/

在这里，作者假设

面额数组按升序排列。

我的问题是为什么面额数组的排序很重要。

下面的链接也采用了类似的假设 （请注意，这里作者正在解决可以进行硬币更换的不同方式，而不是最小硬币更换）

http://www.algorithmist.com/index.php/Coin_Change

现在有了 S1 < S2 < ... < S(M) 的限制，我们的解决方案可以按非递减顺序构建

所以假设如果我的面额数组是无序的，我会得到错误的硬币兑换方式吗？

Answer 1

我的问题是为什么面额数组的排序很重要。

我认为，两种解决方案的顺序并不重要。如果您实施了解决方案，硬币阵列的无序给出了相同的答案。