114. 方格组合计数I(Counting block combinations I)

用灰色方块和最短长度为3的红色方块摆成长度为7的一行,要求任意两个红色方块(长度可以不同)之间至少有一个灰色方块,恰好有17种不同的摆法:

img

若要摆成长度为50的一行,有多少种不同的摆法?

注:尽管上面的例子没有混用不同长度的方格,但这样做是允许的。例如,要摆成长度为8的一行,你可以用红(3)、黑(1)、红(4)。

分析:从114到117连续四道题目都是类似的方块组合问题,可以使用类似的思路加以解决,所以我会在这道题中详细讲解一下共同的分析思路,在剩下三道题中只讲述思路有差异的部分。对于长度为\(n\)的一行灰砖,如果用最小长度为\(m\)的红砖去替换灰砖,可以设其的总的方法数为\(A(n,m)\)。观察题目中列出的例子,我们可以把替换方法分为两种,一种是最右侧以灰砖结尾,设其总的方法法为\(B(n,m)\);一种是最右侧以红砖结尾,设其总的方法数为\(R(n,m)\),则有\(A(n,m)=B(n,m)+R(n,m)\)

先来看以灰砖结尾的情况:如果最右侧是一块灰砖,其长度为一,那么我们只需要关心它左侧的剩余\((n-1)\)块砖,用最小长度为\(m\)的红砖替换有多种方法,即\(B(n,m)=A(n-1,m)\)。再来看以红砖结尾的情况,这又分为两种情况:

则把以上三种情况综合考虑,我们有:

$$ \begin{align*} A\left( n,m \right) &=B\left( n,m \right) +R\left( n,m \right) \\ &=A\left( n-1,m \right) +A\left( n-m-1,m \right) +A\left( n-1,m \right) -A\left( n-2,m \right) \\ &=2A\left( n-1,m \right) -A\left( n-2,m \right) +A\left( n-m-1,m \right) \end{align*} $$

显然我们得到了一个\(A(n,m)\)的递推关系式,还需要考虑一下边界情况。如果\(n<m\),也就是说此时需要替换的一行灰砖的长度比最小长度的红砖还要短,所以不可能用红砖去替换,只能全部用长度为一的灰砖替换,显然替换方法只有一种。如果\(n=m\),也就是需要替换的一行灰砖的长度恰好等于最小长度的红砖的长度,所以要不全部用灰砖替换,要不全部用红砖替换,所以此时总的替换方法有两种。综上,我们有:

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

题目的要求等价于求\(A(50,3)\),使用以上递推关系式,我们可以使用自下而上或者自上而下的动态规划方式来求解此问题。对于这道题目,自上而下的动态规划的代码要更为直观优雅,代码如下:

# time cost = 186 ns ± 1.67 ns

from functools import lru_cache

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

def main():
    return f(50,3)