Problem 5 (Extra credit) Given a number n, consider all 2" sequences of a's and b's that have length n. A sequence is called a good one if and only if there are no two b's in a row anywhere in it. You have to count the total number N(n) of good sequences of length n. Design an efficient algorithm for this problem. Explain why your algorithm yields the correct solution For example, ifn - 4, the followi baaa, abab, baab, baba which yields the answer N(4) -8. Note, that you do not need to print all good sequences; the only thing you have to do is to find the number N(n) ng sequences are good: aaaa, aaab, aaba, abaa, Hints. 1) Could you use divide-and-conquer or dynamic programming? 2) Could you reduce the problem for n to the problems for i n? 3) What characters can be at the end of a good sequence