algorithm - 给定大小的非相邻集的数量

Question

如果给定集合L={1,2,3,...,N}和一个整数k，是否可以有效地计算大小为 k 的“不相邻”子集的数量？如果对于 S 中的每个 x，既不是 x-1 也不是 ，则子集 S 是不相邻的x+1 位于 S 中。

例如，对于 L={1,2,3,4} 和 k=2 ，答案是 3，因为我们有 {1,3},{1,4},{2,4}。对于k=3，答案是零。

一种方法是生成所有大小为 2 的非相邻子集，然后尝试所有可能的并集(因为非相邻集具有其所有子集都不相邻的属性)，但这让我印象深刻浪费，也许有一个甜蜜优雅的有效解决方案。

Answer 1

这样想:如果您知道集合 L'={1, 2, 3, ..., N - 1} 的答案是什么，您可以使用它吗构建L集合答案的信息？ 这个想法是，当您将 N 添加到 L' 时，新的解决方案由 L' 可用的所有子集加上 1 个新子集组成对于 L' 中小于或等于 N - 2*(k - 1) 的每个元素，因此如果 L' 的解> 的大小为 V'，则 V L 的解将为 V = V' + (N - 2* (k - 1))
如果您进一步计算，您会发现解决方案可以表示为前 N - 2k + 2 个自然整数的和。

对于小于或等于N - 2*(k - 1)部分，添加的新数字N只会添加到最终数字较小的子集或等于该表达式的结果，因为正在构建的新子集中必须有 k 个元素(包括数字 N 本身，因此有 k -还需要 1)，彼此之间至少相隔 2 个数字，这使得与数字 N 的距离为 2*(k - 1)，等等表达式。