Student Attendance Record II
It's often helpful to explain the problem to someone else just to see things clearer and come up with a possible solution. Here is what I've just realized.

We don't actually need to keep the complete list during our calculations and only need a single row at a time. Let's reuse it and recalculate the cell values in the loop:

MODULO = 10 ** 9 + 7

class Solution(object):
    def checkRecord(self, n):
        lates = [1, 1, 0]
        absences = [1, 0, 0]

        for i in xrange(2, n + 1):
            sum_lates = sum(lates)
            lates = sum_lates % MODULO, lates[0], lates[1]
            absences = (sum_lates + sum(absences) % MODULO, absences[0], absences[1])

        return (sum(lates) + sum(absences)) % MODULO


I think I've seen this technique before and, if I remember correctly, it is called "Rolling Array".