Choose K different numbers from the set {1, 2, ..., n} so that

Question

Given n and k, k <= n.
In how many ways can we select exactly "k different numbers from the set {1, 2, ..., n}, so that for each selected number 'a, at least one of' a-1, a + 1 is also chosen? dynamic programming with time complexity O (n * k) . Can we do better?

Answer 1

Yes, we just need to do some combinatorics.

Define mileage as the maximum subset of consecutive integers. Let r change from 1 to the floor (k / 2) and summarize the number of subsets with r runs.

To calculate the number of subsets with a given number of runs r, we accept (a) the number of ways to split the run time (b) the number of ways to split the gaps between runs.

For (a) the number of ways to split the integer k into the sum of r integers greater than or equal to 2 is ((k - 2r + (r - 1)) chooses (r - 1)) using the formula standard methods.

For (b) the number of ways to split the integer n - k into the sum of r + 1 integers, where all are non-negative and all except the first and last are positive: ((n - k - (r - 1) + r), choose r )

, O (k ^ 2), r - 1 , r, O (k).