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

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

若要摆成长度为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)\)。再来看以红砖结尾的情况，这又分为两种情况：

• 结尾红砖的左侧是一块灰砖，假设结尾红砖的长度为\(m\)，那么此时的总的替换方法数由左侧剩余的\((n-m)\)块砖决定，则有\(R(n,m)=A(n-m-1,m)\)；
• 结尾红砖的左侧还是红砖，由于题目要求两个红砖间必须间隔一个灰砖，所以这种情况下这块结尾红砖应该是一块红砖而不是两块红砖，我们可以把它看作是一块长度为一的红砖接在了一个长度为\((n-1)\)红灰砖组合的后面，且这个红灰砖组合的结尾是一块红砖，所以此时有\(R(n,m)=R(n-1,m)=A(n-1,m)-B(n-1,m)=A(n-1,m)-A(n-2,m)\)。

则把以上三种情况综合考虑，我们有：

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

题目的要求等价于求\(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)