116. 红色、绿色或蓝色的地砖(Red, green or blue tiles)

将一行五块灰色方形地砖的一部分替换成红色(长度为2)、绿色(长度为3)或蓝色(长度为4)的地砖。如果只使用红色地砖,一共有7种不同的替换方式:

img

如果只使用绿色地砖,一共有3种不同的替换方式:

img

如果只使用蓝色地砖,一共有2种不同的替换方式:

img

假定颜色不能混合使用,则一共有\(7+3+2=12\)种方式替换一行五块灰色地砖。假定颜色不能混合使用,且至少使用一种彩色地砖,一共有多少种方式替换一行五十块灰色地砖?

分析:这道题目至少有两种思路,一种是使用我们在解决前两道题时发展出来的动态规划的思路,用递推关系式求解,另一种是组合学的思路,下面我们分别来看一下:

一、动态规划思路

这道题与上两道题的显著区别是上两道题的地砖长度并不固定,而这道题的地砖长度只有一至四四种选择;此外,这道题因为用颜色进行区分,不同长度地砖之间也不需要保留间隔,实际上使得问题更加简单化了。设\(A(n,m)\)表示仅用长度为\(m\)与长度为一的地砖去填充长度为\(n\)的一行的总方法数,则可分两种情况:

综合以上两种情况,有:

$$ A(n,m)=A(n-m,m)+A(n-1,m) $$

易知当\(n<m\)时,也就是需要填充的长度小于彩色地砖的长度时,显然只能使用灰色地砖去填充了,则只有一种填充方法。则有:

$$ A\left( n,m \right) =\left\{ \begin{matrix} A\left( n-1,m \right) +A\left( n-m,m \right)& n\ge m\\ 1& n<m\\ \end{matrix} \right. $$

根据题目的要求,我们只需要求出\(A\left( 50,2 \right) +A\left( 50,3 \right) +A\left( 50,4 \right)\)即可。需要注意的是,根据题目示例,全部使用灰色地砖填充的情况应该排除,所以三种分类各排除一种情况,总共排除三种情况,即可得到题目的解。

二、组合学思路

下面介绍组合学思路,我们首先看一下题目中的例子,总共有五块灰色地砖,假设用长度为二的红色地砖去替换,那么最多使用\(int(5/2)=2\)块红色地砖。先看只使用一块红色地砖的情况,此时还有\(5-2=3\)块灰色地砖,因此总共有\(1+3=4\)个位置需要放上红色地砖,一旦红色地砖的位置确定了,剩下三块灰色地砖的位置也就确定了。所以这种情况总共有\(C_4^1=4\)种替换方法。再来看使用两块红色地砖的情况,此时有\(5-2\times2=1\)种灰色地砖,总共有\(2+1=3\)个位置需要放上红色地砖,同理总共有\(C_3^2=3\)种替换方法。把上面两种方法加起来,所以一行五块灰色地砖用长度为二的红色地砖替换的方法共有7种。

把上面的推理逻辑一般化:对于一行长度为\(n\)的灰色地砖,使用长度为\(m\)的小地砖去替换,显然有\(n\ge m\),则我们最多使用\(\lfloor{n/m}\rfloor\)种小地砖。假设使用了\(k\)块小地砖,则剩余的可以容纳灰色地砖的位置有\(n-km\),总共可以容纳小地砖的位置有\(k+n-km\)种,我们需要从中选出\(k\)个位置用来容纳小地砖,则总的组合数为\(C(k+n-km,k)\)种。我们把\(1\le k\le \lfloor{n/m}\rfloor\)范围内组合数都求出来并加总,即为把长度为\(n\)的灰色地砖用长度为\(m\)的小地砖去替换的所有方式。代码如下:

# approach 1, time cost = 583 ns ± 2.65 ns

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,m):
    if n < m:
        return 1
    else:
        return f(n-m,m)+f(n-1,m)

def main(n=50):
    return f(n,2)+f(n,3)+f(n,4)-3

# approach 2, time cost = 426 µs ± 3.03 µs

from scipy.special import comb

def replaced_ways(n,m):
    w = 0
    for k in range(1,n//m+1):
        t = k + n - k*m
        w += comb(t,k)
    return w

def main(n=50,length=[2,3,4]):
    ways = [replaced_ways(n,x) for x in length]
    return sum(ways)