117. 红色、绿色和蓝色的地砖(Red, green, and blue tiles)

使用灰色地砖、长度为2的红色地砖、长度为3的绿色地砖、长度为4的蓝色地砖的组合,一共有恰好15种不同的方式铺满长度为5的一行:

img

一共有多少种不同的方式铺满长度为50的一行?

注:这道题和第116题有关。

分析:这道题与第116题仅一字之差,但实际上也可以沿用我们在前三道题中发展出来的思路。假设\(F(n)\)表示把长度为\(n\)的一行用四种长度的地砖去替换,则题目要求的实际上就是\(F(50)\)。我们仍然根据最右侧结尾的地砖来分类,则可以分成四类:

因此易知:

$$ F\left( n \right) =F\left( n-1 \right) +F\left( n-2 \right) +F\left( n-3 \right) +F\left( n-4 \right) $$

\(F_1=1,F_2=2,F_3=3,F_4=4\),则可以根据以上递推式求解\(F_{50}\),代码如下:

# time cost = 16.9 µs ± 82.7 ns

def main(n=50):
    arr = [1,2,4,8]
    for _ in range(n-4):
        arr.append(sum(arr[-4:]))
    return arr[-1]