algorithm - 相邻位计数

Question

这里是 problem来自 spoj 声明

For a string of n bits x1,x2,x3,...,Xn the adjacent bit count of the string (AdjBC(x)) is given by

X1*X2 + X2*X3 + X3*X4 + ... + Xn-1 * Xn

which counts the number of times a 1 bit is adjacent to another 1 bit. For example:

AdjBC(011101101) = 3
AdjBC(111101101) = 4
AdjBC(010101010) = 0

问题是:编写一个程序，将整数 n 和 k 作为输入，并返回满足 AdjBC(x) = k 的 n 位(共 2ⁿ)的位串 x 的数量。

我不知道如何解决这个问题。你能帮我解决这个问题吗？

谢谢

Answer 1

通常在组合问题中，查看它产生的值集会有所帮助。我使用蛮力计算了下表:

  k   0   1   2   3   4   5   6
n +----------------------------
1 |   2   0   0   0   0   0   0
2 |   3   1   0   0   0   0   0
3 |   5   2   1   0   0   0   0
4 |   8   5   2   1   0   0   0
5 |  13  10   6   2   1   0   0
6 |  21  20  13   7   2   1   0
7 |  34  38  29  16   8   2   1

第一列是熟悉的斐波那契数列，满足递归关系f(n, 0) = f(n-1, 0) + f(n-2, 0)

其他列满足递推关系f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + f(n - 2, k) - f (n - 2, k - 1)

有了这个，你可以做一些动态规划:

INPUT: n, k
row1 <- [2,0,0,0,...] (k+1 elements)
row2 <- [3,1,0,0,...] (k+1 elements)
repeat (n-2) times
  for j = k downto 1 do
    row1[j] <- row2[j] + row2[j-1] + row1[j] - row1[j-1]
  row1[0] <- row1[0] + row2[0]
  swap row1 and row2
return row2[k]