n*3尺寸墙面用1*3/2*3/3*3砖块填充的排列数及递推关系求解

递推式正确性判断 #

你推导的递推式T(n) = T(n-1) + 2*T(n-2) + 7*T(n-3)完全正确，推导逻辑也符合组合计数的无重复、无遗漏原则：

• T(n-1)项：对应墙面最上方1行用1块横置1*3砖填充，剩余(n-1)*3区域的排列数为T(n-1)，系数为1。
• 2*T(n-2)项：对应墙面最上方2行没有水平分割线，仅能以「2块横置1*3砖」或「1块横置2*3砖」两种方式填充，剩余(n-2)*3区域的排列数为T(n-2)，因此系数为2。
• 7*T(n-3)项：对应墙面最上方3行没有水平分割线，所有不可拆分的填充方案共7种（横竖组合+3*3砖填充），剩余(n-3)*3区域的排列数为T(n-3)，因此系数为7。

配套边界条件 #

要让递推式正常计算，需要补充以下边界值：

• T(0) = 1：空墙面默认1种合法填充方案，用于递推初始计算
• T(1) = 1：仅能放置1块横置1*3砖
• T(2) = 2：两种填充方案，和T(n-2)的系数逻辑一致

我们可以用小值验证递推结果的正确性：

• T(3) = T(2) + 2*T(1) + 7*T(0) = 2 + 2*1 +7*1 = 11，和手动枚举的3行墙面填充总数一致
• T(4) = T(3) + 2*T(2) + 7*T(1) = 11 + 4 +7 = 22，符合实际计数结果

总排列数计算方式 #

对给定的n值，从边界条件出发按递推式迭代计算即可得到总排列数，时间复杂度为O(n)，空间复杂度可优化到O(1)。

内容的提问来源于stack exchange，提问作者Sky