砖块在墙上的排列方式总共有多少种？
Total number of ways in which the bricks can be arranged on the wall?
假设我们有一堵n*3大小的墙，有1*3、2*3、3*3大小的砖块，砖块可以横放也可以竖放，将砖块填满墙壁的总共有多少种方法？这个问题的递归关系是什么？
我认为是 T(n) = T(n-1)+ 2T(n-2)+ 7T(n-3)，因为 T(n-2) 我们有 1x3+1x3 或 2x3 所以 2T(n-2)。对于三个，1x3+1x3+1x3、1x3+2x3 或 2x3+1x3 和水平相同，加上 3x3 所以我们有 7dp(n-3)，这是正确的吗？
谢谢！
这几乎是正确的，但它多算了几个术语。例如，T(n-2) 的解决方案 S 可以在其后添加两个垂直的 1-brick 以成为 T(n) 的解决方案。如果您在 S 之后添加一个 1-brick，它是 T(n-1) 的解决方案，因此 S + 两个 1-brick 的排列被计入您的 T(n-2) 和 T(n-1) 项中。
相反，想想 T(n) 的解 S 如何在右边结束。您可以证明 (n-1) x 3 S 的初始段对 T(n-1) 当且仅当 S 的最终块是垂直 1 块时才有效。
否则，S的(n-2) x 3初始段什么时候是S的最长有效初始段？正是当 S 以垂直 2 块结束时（如果它以两个垂直 1 块结束，则最长有效初始段的长度为 n-1，我们已经计算过了）。
最后的情况是n-3：找出最后3 x 3 space 有多少种可能的配置使得S的最长有效初始段长度为n-3。作为提示：答案，称它为 'c'，小于 7，如您所示，它是 3 x 3 space 的所有配置的计数。这些为您提供递归系数，T(n) = T(n-1) + T(n-2) + c*T(n-3)，以及 n = 1、2 和 3 的适当基本情况。
假设我们有一堵n*3大小的墙，有1*3、2*3、3*3大小的砖块，砖块可以横放也可以竖放，将砖块填满墙壁的总共有多少种方法？这个问题的递归关系是什么？
我认为是 T(n) = T(n-1)+ 2T(n-2)+ 7T(n-3)，因为 T(n-2) 我们有 1x3+1x3 或 2x3 所以 2T(n-2)。对于三个，1x3+1x3+1x3、1x3+2x3 或 2x3+1x3 和水平相同，加上 3x3 所以我们有 7dp(n-3)，这是正确的吗？
谢谢！
这几乎是正确的，但它多算了几个术语。例如，T(n-2) 的解决方案 S 可以在其后添加两个垂直的 1-brick 以成为 T(n) 的解决方案。如果您在 S 之后添加一个 1-brick，它是 T(n-1) 的解决方案，因此 S + 两个 1-brick 的排列被计入您的 T(n-2) 和 T(n-1) 项中。
相反，想想 T(n) 的解 S 如何在右边结束。您可以证明 (n-1) x 3 S 的初始段对 T(n-1) 当且仅当 S 的最终块是垂直 1 块时才有效。
否则，S的(n-2) x 3初始段什么时候是S的最长有效初始段？正是当 S 以垂直 2 块结束时（如果它以两个垂直 1 块结束，则最长有效初始段的长度为 n-1，我们已经计算过了）。
最后的情况是n-3：找出最后3 x 3 space 有多少种可能的配置使得S的最长有效初始段长度为n-3。作为提示：答案，称它为 'c'，小于 7，如您所示，它是 3 x 3 space 的所有配置的计数。这些为您提供递归系数，T(n) = T(n-1) + T(n-2) + c*T(n-3)，以及 n = 1、2 和 3 的适当基本情况。