114. Counting block combinations I.md

114. Counting block combinations I

Question

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one grey square. There are exactly seventeen ways of doing this. How many ways can a row measuring fifty units in length be filled?

Solution

from functools import lru_cache

def p114(n=50):
    @lru_cache(maxsize=None)
    def f(n):
        if n <= 2: return 1
        res = f(n - 1)           # a black first
        for i in range(3, n):
            res += f(n - i - 1)  # red followed by a black
        return res + 1           # all red no black

    return f(n)

Answer

16475640049