SPOJ - GNYR09F (Adjacent Bit Count)

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.