c# - 砌砖在墙上的总布置方式是多少？

有一堵墙，墙的大小为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];
}

但这仅仅是一个组合:猜测+直觉。我不完全了解此解决方案。为什么是table[i] = table[i-1] + table[i-4]？

看起来不像是找零硬币的问题吗？

使用a种类的硬币来更改数量n的方法数量等于:
使用除第一类硬币以外的所有硬币来改变金额a的方法的数量，以及使用所有a - d类型的硬币来改变金额n的方法的数量，其中d是第一类硬币的面额。

但是我也不明白我们怎么能用这个想法解决最初的问题

最佳答案

如果少于4列，显然只有一种方法来布置积木:

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

但是，有两种方法可以为第4列布置砖块。
方法1-只需将一列添加到3列的正确解决方案中即可:

1234
1234
1234
1234

方法2-删除现有的三列并放置四块水平砖:

1111
2222
3333
4444

相同的逻辑适用于所有后续列-您可以为N-1进行所有适当的排列并为它们中的每一个添加一个列，也可以为N-4进行所有正确的排列并水平放置四块砖。
解决方案之所以如此简单，是因为该问题的一种推导-您可以放置​​4个水平砖或4个垂直砖，因为放置1个水平砖将使放置垂直成为不可能，反之亦然。
如果墙仍然是4xN，而砖分别是2x1和1x2，则此任务将更加困难。

关于c# - 砌砖在墙上的总布置方式是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38824236/