拆分自然数：纯while实现 (Part 2 - 实现)

核心提示： 在Jeff的题目里面，我们可以通过一些例子来观察scan应有的条件，拆分自然数：纯while实现 (Part 2 - 实现)(4)，对于(5, 3, 1, 3)的输入，[1, 1, 3]和[1, 2, 2]是两个有效解，因为递归时桟信息是暗含的，你无法直接访问，也就是说对[1, 1, 3]

在Jeff的题目里面，我们可以通过一些例子来观察scan应有的条件。对于(5, 3, 1, 3)的输入，[1, 1, 3]和[1, 2, 2]是两个有效解，也就是说对[1, 1, 3]进行scan时，应该跳过末尾的3，而定位到中间的1上面去。那么为什么[1, 1, 4]不是合法的迭代结果呢？一方面4越了上界，另一方面总和超出sum了，而最低位的迭代是无法通过后面的fill来重新调整总和的。假如我们再考虑一下(5, 3, 1, 4)的输入，那么我们可以知道4越了上界这个条件其实是可有可无的，总和超出sum这个条件才是关键的。

那为什么[1, 1, 3]迭代为[1, 2, *]是合法的，但是[1, 2, 2]迭代为[1, 3, *]就不是合法的呢？通过观察我们可以得知，因为[1, 1, 3]中末两位相差2，所以我们可以确信进行[1, 1 + 1, 3 - 1]调整后，这仍然是一个不下降序列。但是[1, 2, 2]就不符合这个条件了，因为[1, 2 + 1, 2 - 1]不是一个不下降序列。为此，我们可以认为寻找相邻两个相差大于或等于2的位，就是scan的目标。

接着我们再来观察一个例子，输入为(15, 3, 4, 6) ，初始解为[4, 5, 6]，还能迭代下去吗？用上面的scan判定是无法迭代下去了，因为任何两位之间都仅仅相差1。但实际上，还有一个解是[5, 5, 5]。问题出在哪呢？我们之前的观察忽略了非相邻位的调整。没错，[4 + 1, 5 - 1, 6]和[4, 5 + 1, 6 - 1]都不是合法解，但[4 + 1, 5, 6 - 1]是合法解，这就是我们所忽略了的。因此，scan需要寻找的不是相差大于或等于2的相邻两位，而是相差大于或等于2的任意两位，并且要求这两位尽量低位（因为迭代优先从较深节点展开）。这看起来使得scan的逻辑复杂无比，首先要把任何相差大于或等于2的两位配对找出来，再在里面找最低位的一对。

实际上，不下降序列的特性为我们很好地解决了这个问题，我们只需要利用scan找到首个跟末位相差大于或等于2的位就可以了。例如[1, 2, 3, 4, 5, 6]，我们知道[1, 6], [2, 6], ..., [4, 6], [1, 5], [2, 5], ..., [1, 3]都是符合条件的配对，但最靠近低位的一定是[*, 6]。我们假设[x, 5]符合条件，对于同一个x，[x, 6]一定是符合条件的，同理[x, 4], [x, 3], ...也不用看了，只要针对[x, 6]找到x最大的合法取值就可以了。为此，我们可以写下简单的scan继续执行条件，那就是array[i] > array[n - 1] - 2。

看到这里，相信大家都明白了为什么我说scan的一个判定条件如此重要，因为它肩负着不依赖于上下文信息进行剪枝的任务——不知道下界与上界为何物，也不知道整个数组的sum是多少，所有这些状态信息都暗含在上一次fill好的数组中，无需为scan提供额外的信息（包括缓存信息）它就能工作。scan结束后，它只需要为fill提供两个正确的信息——i和sum，随后fill必然能够给出下一个迭代解的低位。

最后，我来解释一下为什么不应该缓存下界和上界，只要缓存sum。首先，我们要为缓存这件事达成一个共识，那就是只有当一个东西会一次写入多次读取时，我们才需要进行缓存。下界信息是一定不需要混存的，在首次fill后每一位的下界就确定下来了，随后迭代总是在某一位加一，下界这个值永远无需被重新访问，也就没必要缓存下来。同理，上界信息其实也在首次fill后确定下来了，并且随着每一次fill动态调整，因为array[n - 1]的上界就是它自身，而其它array[i]的上界必然小于或等于array[n - 1] - 2，这个逻辑已经暗含在scan里面了，自然就没必要缓存上界了。最后，sum的缓存是我在scan里面没做的，所以每次scan都要重新计算sum值，缓存sum值有助于性能的提升。

P.S.临摹其实是会限制你的思维的。由于Jeff的DoBest使用了itemMinInclusive和itemMaxInclusive进行剪枝，这影响到其它人在做递归展开时也优先考虑用同样的方法进行剪枝，然而在递归中最好的剪枝方法并不一定在展开后仍然是最好的，因为递归时桟信息是暗含的，你无法直接访问，在展开后你就能直接访问了。