我正在解决 algoexpert.io 编码挑战，但无法理解标题为 的问题之一的建议解决方案不可施工的改变
这是挑战问题：
给定一个正整数数组，表示您的硬币的价值
拥有，编写一个返回最小变化量的函数（
最低金额），您cannot创造。给定的硬币可以有
任何正整数值并且不一定是唯一的（即，您可以有
多枚相同价值的硬币）。
例如，如果给你硬币 = [1, 2, 5]，则最小
您无法创建的更改数量为 4。如果您没有获得
硬币，您不能创建的最小找零金额是 1。
// O(nlogn) time, O(n) size.
function nonConstructibleChange(coins) {
coins = coins.sort((a, b) => a - b); // O(nlogn) time operation
let change = 0;
for (coin of coins) {
if (coin > change + 1) return change + 1;
change += coin;
}
return change + 1;
}
我的问题
我不完全确定该解决方案的作者是如何得出这样的直觉的
if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.
我可以看到它是如何跟踪的，并且该算法确实通过了所有测试，但我想更多地了解可以用来设计此规则的过程。
感谢您花时间阅读问题！
这也花了我一段时间，但这就是我的理解方式：
假设您已经证明自己可以赚 1-8 美分。
您进入下一次迭代并想知道是否可以赚到 9 美分。因此，您迭代到排序列表中的下一个新硬币。
如果新币
- 你知道你可以赚 9 美分这一事实。
- 例如，如果新硬币是 5：使用该新硬币并从您想要制作的总数中减去它。 9 - 5 = 4。然后不管你之前做4的方式如何，再做一次。 （你已经证明你可以赚1-8美分）
如果新币 == 9:
- 你知道你可以赚 9 美分这一事实。
- 只需使用 9 分硬币
如果新币 > 9：
- 你知道一个事实，你赚不到 9 美分
- 这是因为你不能使用新硬币。例如，当您尝试制作 9 美分时，一枚 10 美分的硬币对您来说毫无用处，因为它太大了（无法制作 9）
-
如果你不使用新硬币，你也完蛋了因为如果你把目前为止看到的所有硬币加起来，你只能制作 8 个（不能制作 9 个）
这就是变化 + 1 的来源。 （你的变量变化= 8）
if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
