從集合{1，2​​，...，n}中選擇K個不同的數字，使得

Question

給定n和k，k < = n。
在多少種方式中，我們可以從集合{1,2，...，n}中精確選擇'k'個不同的數字，從而對於每個選擇的數字'a'至少有一個'a-1'，'a + 1'也被選中？ 與時間複雜度爲O（n * K）的動態規劃的解決方案是known.Can我們做的更好？

Answer 1

是的，我們只需要做一些組合。

將運行定義爲連續整數的最大子集。我們讓r的範圍從1到floor（k/2）並且將r個子集的數目相加。我們採取（a）劃分運行長度時間的方法的數量（b）劃分運行之間的間隙的方法的數量。爲了計算具有給定運行次數r的子組的數量，我們採取（a）劃分運行長度時間的方法的數量。對於（a），將整數k劃分爲大於或等於2的整數r的整數的方式的數量是（（k-2r +（r-1））個選擇（r-1））通過標準技術。對於（b），將整數n-k劃分爲r + 1個整數（其全部是非負的並且除了第一個和最後一個都是正的除外）的和的方式的數量是（（n-k-（r） - 1）+ r）選擇r）。天真的是，這個公式需要O（k^2）的算術運算，但是如果我們用r-1的二項式係數來計算r的那個，那麼運行時間就變成O（k）的算術運算。