I am trying to solve this problem on spoj . By using tutorial in this Link I am able to figure out this recurrence.
***** AA*** AA*** AA*** A****
***** = AA*** + A**** + AA*** + A****
***** AA*** A**** A**** AA***
***** AA*** AA*** A**** AA***
f(n) = f(n-2) + h(n-1) + g(n-1) + g(n-1).
But I can’t understand how to solve the recurrence for h(n-1) and g(n-1).