从集合{1, 2, ..., n}中选择K个不同的数字，使得...

Question

4

给定n和k，其中k≤n。
从集合{1,2,…,n}中选择恰好'k'个不同的数字的方式有多少种，使得对于每个选定的数字'a'，至少选择其中一个'a-1'或'a+1'？已知时间复杂度为O(n*k)的动态规划解决方案，我们能做得更好吗？

- Abhi

1

给定 n 和 K 作为输入。我们必须选择恰好 k 个不同的数字。 - Abhi

如果您能证明时间复杂度也是 Ω(n*k)，那么时间复杂度将是 Θ(n*k)，这意味着您无法做得更好。 - Christos

你能展示一下O(nk)算法吗？（可能有一些改进） - Abhishek Bansal

请问在n个数字中，选择k个数字并且这k个数字之间至少有m个连续数字的方案数有多少种？ - גלעד ברקן

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

是的，我们只需要进行一些组合计算。

将一组连续的整数定义为一个“run”。我们让r从1到k/2下取整，并计算具有r个“run”的子集的数量之和。

要计算具有给定数量的“run” r的子集的数量，我们需要（a）将“run”长度分成若干部分的方法数乘以（b）将“run”之间的空隙分成若干部分的方法数。

对于（a），将整数k分成r个大于或等于2的整数的方法数是通过标准技术得出的，即((k-2r+(r-1)) choose (r-1))。

对于（b），将n-k分成r+1个整数的方法数，其中所有整数均为非负整数，除第一个和最后一个以外的所有整数均为正整数，即((n-k-(r-1)+r) choose r)。

朴素地说，这个公式需要O(k^2)次算术运算，但如果我们使用r-1的二项式系数来计算r的二项式系数，则运行时间变为O(k)次算术运算。