|
Count strings without consecutive 1s
Problem: Given an integer N, count all the strings without consecutive 1s.
Assume that the strings are made up of only 0s and 1s
Solution: Let a be the number of strings without consecutive 1s and with last-character = 0
And let b be the number of strings without consecutive 1s but with last-character = 1
For a(k), we can append either 0 or 1 and the resulting strings would still be without consecutive 1s
For b(k), we can only append a 0 at the end.
Recursively, a(k+1) and b(k+1) can be written as:
a(k+1) = a(k) + b(k)
b(k+1) = a(k)
This is a perfect candidate for dynamic programming.
int countStringsWithout1s(int n)
{
int a[n];
int b[n];
a[0] = 1;
b[0] = 1;
for (int i = 1; i < n; i++)
{
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}
return a[n-1] + b[n-1];
}
|
