Problem Statement:

SPOJ - Adjacent Bit Count (GNYR09F)

Summary:

In a string of bits s, we denote adj(s) as the number of pairs of adjacent bits with both bits are 1. Given n the length of string and k = adj(s), find the number of ways such strings can be constructed.

( \( n \leq 100 \) )

Solution:

The solution is by a DP approach. Let W(b, k, len) be the number of ways of constructing a string s of length len such that it ends with bit b, and have adj(s) = k. Then we have:

W(0, k, len) = W(0, k, len-1) + W(1, k, len-1)

W(1, k, len) = W(0, k, len-1) + W(1, k-1, len-1)

From this relationship we can work out the values using a bottom up DP in O(nk) time.