javascript - 如何为 Algoexpert.io 的 Non-Constructible Change 挑战设计这种解决方案

Question

我正在处理 algoexpert.io 编码挑战，但我无法理解标题为 的问题之一的建议解决方案。不可构造的变化
这是挑战问题:
给定一个代表硬币值(value)的正整数数组
占有，写一个函数返回最小的变化量(
您无法创建的最低金额)。给定的硬币可以有
任何正整数值并且不一定是唯一的(即，您可以拥有
多个相同值(value)的硬币)。
例如，如果给定硬币 = [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`.

我可以看到它是如何跟踪的，并且确实该算法通过了所有测试，但我想了解更多关于我可以用来设计这个规则的过程。
感谢您花时间阅读问题!

Answer 1

这个也花了我一段时间，但这就是我理解它的方式:
假设你已经证明你可以赚 1-8 美分。
你进入下一个迭代，想知道你是否能赚到 9 美分。所以你迭代到排序列表中的下一个新硬币。
如果新币 < 9:

你知道一个事实，你可以赚 9 美分。

例如，如果新硬币是 5:使用该新硬币并将其从您尝试制作的总数中减去。 9 - 5 = 4。然后，无论您以前制作 4 的方式，只需再次执行此操作即可。 (你已经证明你可以赚 1-8 美分)

如果新币 == 9:

你知道一个事实，你可以赚 9 美分。

只需使用 9 美分硬币

如果新币 > 9:

你知道你不能赚 9 美分

这是因为 你不能使用新硬币 .例如，一个 10 美分的硬币对你来说是无用的，因为它太大了(不能赚 9)

不使用新币你也完蛋了因为如果你把迄今为止看到的所有硬币加起来，你只能赚到 8 个(不能赚到 9 个)

这就是 change + 1 的来源。 (您的变量更改 = 8)

if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.