给定n和k,其中k≤n。
从集合{1,2,…,n}中选择恰好'k'个不同的数字的方式有多少种,使得对于每个选定的数字'a',至少选择其中一个'a-1'或'a+1'?已知时间复杂度为O(n*k)的动态规划解决方案,我们能做得更好吗?
给定n和k,其中k≤n。
从集合{1,2,…,n}中选择恰好'k'个不同的数字的方式有多少种,使得对于每个选定的数字'a',至少选择其中一个'a-1'或'a+1'?已知时间复杂度为O(n*k)的动态规划解决方案,我们能做得更好吗?
是的,我们只需要进行一些组合计算。
将一组连续的整数定义为一个“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)次算术运算。
Ω(n*k)
,那么时间复杂度将是Θ(n*k)
,这意味着您无法做得更好。 - Christos