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

Question

如果给定集合 L={1,2,3,...,N} 和一个整数 k，是否可以有效地计算大小为 k 的“非相邻”子集的数量？子集 S 是不相邻的，如果对于 S 中的每个 x，既不是 x-1 也不是 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 个数字，这使得 2*(k - 1) 与数字 N 的距离，等等表达式。