砖块在墙上的排列方式总共有多少种？

Question

有一面墙的大小是4xN。我们有无限多块砖，大小分别为4x1和1x4。砖块在墙上的排列方式总数是多少，这样每次都会出现新的配置？

对于N=1，砖块只能以1格式放置。对于N=7，我们可以铺设砖块的方法之一是

有5种方法可以排列砖块N=7

我使用动态规划来解决这个问题：

static int computeBricks(int n)
{
    if(n <= 3) { return 1; }

    int[] table = new int[n+1];

    table[0] = 1;
    table[1] = 1;
    table[2] = 1;
    table[3] = 1;

    for(int i = 4; i <= n; ++i)
    {
        table[i] = table[i-1] + table[i-4];
    }

    return table[n];
}

但这只是一个组合：猜测直觉。我不完全理解这个解决方案。为什么表[i]=表[i-1]表[i-4]？

看起来不是硬币兑换问题吗？

使用n种硬币改变数量的方法数等于：使用除第一种硬币之外的所有硬币改变数量的方法数，加上改变数量的方法数a-d使用所有n种硬币，其中d是第一种硬币的面额。

但我也不明白我们如何用这个想法来解决最初的问题

Answer 1

  f(n) = f(n-1) + f(n-4)  if n >= 4 <p>
  f(n) = 1 if 0  <= n < 4 

Answer 2

如果你有少于4列，显然只有一种方法来排列砖块：

1, 12, 123
1, 12, 123
1, 12, 123
1, 12, 123

然而，有两种方法可以为第四根柱子布置砖块
方法1-只需将一列添加到包含3列的正确解决方案中：

1234
1234
1234
1234

方法2-移除现有的三根柱子，放置四个水平砖：

1111
2222
3333
4444

同样的逻辑也适用于所有后续列——你可以选择N-1的所有适当排列，并在每个列中添加一列，或者选择N-4的所有正确排列，并水平放置四块砖
解决方案之所以如此简单，是因为问题的一个推论——你可以放置4块水平砖或4块垂直砖，因为放置1块水平砖将使垂直放置变得不可能，反之亦然
如果墙仍然是4xN，但砖块是2x1和1x2，那么这项任务会困难得多。

Answer 3

完整地说，你可以使用简单的计数技术，不需要算法。

你有N个斑点。有两种方法可以填充这些点：一次一个（垂直砖），或一次填充4个连续点（水平砖）。你可以重新表述：这是你可以在N-（3*K）垂直砖块中放置K一堆4个水平砖块（K介于0和N/4）的方法的数量（对于每一堆4个水平砖块，与1个垂直砖块相比，你会失去3个斑点-这是你[N-4]的位置来自原始算法）。

让我们用一个例子来说明这一点。首先，我在下面使用的符号choose（n，k）是数学组合“n choose k”，即。

现在让我们深入到这个例子中。你能用N=15spot做什么？

>

你有一个K=0水平砖堆（H）和15个垂直砖堆（V）：VVVVVVVVVVVV。执行此操作的方法的数量是选择（15,0）=1

或者你可以把K=1H放在某个地方（用1h替换4v会失去三个位置）：vvvvv。实现这一点的方法有很多：选择（15-3,1）=选择（12,1）=12

或者您可以放置K=2H（通过将8 V替换为2 H，您将失去六个点）：VVHVVVVVH。这样做的方法的数量是选择（15-6,2）=选择（9,2）=36

或者你可以把K=3H（用3h替换12v会损失9个点）：hvhv。实现这一点的方法有很多：选择（15-9,3）=选择（6,3）=20

就是这样，你已经达到了水平桩的最大数量（max K=15/4=3）。然后，您只需将所有这些加起来，就可以得到填充这些位置的方法总数：1 12 36 20 = 69。

下面是直接从这个解释中得出的一般公式：

3601cc2c5.gif" width="100%" height="100%" />

这最终导致：