I just gave the ZIO here in my city at 5 in the evening and wrote my final answers on my palm. If someone can cross-check my answers and provide some input, it would be highly appreciated. I am writing the question as far as I can remember, so people who didn’t give the exam can also give it a go.
- Let there be a list of length n, [x_1, x_2, … x_n], where x_i can be between 0 and k inclusive. A sequence is called good if 0,1,0 are not present consecutively in a list. Find the number of good lists, good(n,k), given n and k.
i) good(7,1) = 71
ii) good(7,3) = 15899
iii) good(20,1) = 524308
I don’t know if these are the correct answers, but I used some sort of recursion to come up with these answers. I don’t know that much coding, so I am not so proficient with dynamic programming but let us see if I am correct.