Thought Process

We make a dynamic programming function compute(d, a, l) where d = days in total, a = number of absences, l = number of lates, which returns the total number of strings that win a prize.

1. if a == 3

   • this string will not result in a prize

2. if l > 1

   • this string will not result in a prize

3. if d = 0

   • we have reached the end of the string and not encountered any problem, hence we get a prize

Then we add the following to the running total

1. total += compute(d-1, 0, l)

   • if the student is on-time (absence goes to 0, late stays the same)

2. total += compute(d-1, a + 1, l)

   • if the student is absent (absence + 1, late stays the same)

3. total += compute(d-1, 0, l + 1)

   • if the student is late (absence goes to 0, late + 1)

then we can use the inbuilt @cache function from functools module to greatly speed things up because if we encounter a different string, with the same number of lates and absences on a current day, then they can be evaluated the same from that day onward!

Note that compute(30, 0, 0) will result in the answer as we are "counting down" from 30 to 0