algorithm - 砖在墙上的排列方式有几种？

Question

假设我们有一堵墙，n*3大小为 ,1*3和2*3的3*3砖块可以水平和垂直放置，那么将砖块填满墙的方式有多少？这个问题的递归关系是什么？

我想是的T(n) = T(n-1)+ 2T(n-2)+ 7T(n-3)，因为对于T(n-2)我们来说还是1x3+1x3有的。对于三个, ,或与水平相同, 加上所以我们有, 这是正确的吗？2x32T(n-2)1x3+1x3+1x31x3+2x32x3+1x33x37dp(n-3)

谢谢！

标签： algorithmrecursiondynamic-programming

Answer 1

这几乎是正确的，但它高估了几个术语。例如，T(n-2) 的解 S 可以在其后添加两个垂直的 1-bricks 以成为 T(n) 的解。如果您在 S 之后添加一个 1-brick，它是 T(n-1) 的解决方案，因此您的 T(n-2) 和 T(n-1) 项中计算了 S + 两个 1-brick 的排列。

相反，请考虑 T(n) 的解 S 如何在右侧结束。当且仅当S 的最终块是垂直 1 块时，您可以证明(n-1) x 3S 的初始段对 T(n-1) 有效。 否则，S 的初始段何时是S 的最长有效初始段？恰好当 S 以垂直 2 块结束时（如果它以两个垂直 1 块结束，则最长的有效初始段的长度为 n-1，我们已经计算过了）。
(n-2) x 3

最后一种情况是 n-3：找出最后一个3 x 3空间有多少种可能的配置，使得 S 的最长有效初始段的长度为 n-3。作为提示：答案，称为“c”，小于 7，正如您所展示的，它是3 x 3空间所有配置的计数。这些为您提供了递归系数 T(n) = T(n-1) + T(n-2) + c*T(n-3)，以及 n = 1、2 和 3 的适当基本情况。