c# - 砖 block 在墙上的排列方式总共有多少种？

Question

有一堵大小为4xN的墙.我们有无数 block 大小为 4x1 的砖 block 和 1x4 .砖 block 在墙上的排列方式总共有多少种，每次都会产生新的排列方式？

对于 N = 1 , 砖可以铺在1格式而已。对于 N = 7 ，我们可以铺砖的方法之一是

N = 7 的积木有 5 种排列方式

我用动态规划解决了这个问题:

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是第一种硬币的面额。

但是我也不明白我们怎么可以用这个思路来解决原来的问题

Answer 1

为了完整起见，您可以使用简单的计数技术来做到这一点，不需要算法。

你有N个点。您有两种填充 Blob 的方法:一次填充一种(垂直砖 block )，或者一次性填充 4 个连续的 Blob (水平砖 block )。您可以重新表述:这是放置 K 堆 4 block 水平砖 block 的方式的数量(K 介于 0 和 N/4 之间) 在 N-(3*K) 垂直砖 block 中(对于每堆 4 block 水平砖 block ，与 1 block 垂直砖 block 相比，你失去了 3 个位置 - 这就是你的 [n-4] 的来源在你原来的算法中)。

让我们用一个例子来说明。首先，我在下面使用的符号 choose(n, k) 是数学 combination “n 选择 k”，即

现在让我们深入这个例子。你可以用 N = 15 点做什么？

• 您有 K = 0 堆水平砖 block (H) 和 15 block 垂直砖 block (V):VVVVVVVVVVVVVVVV。这样做的方法有 choose(15, 0) = 1

• 或者您可以将 K = 1 H 放在某处(将 4 V 替换为 1 H 会失去三个位置):VVVVHVVVVVVVV。这样做的方法数是 choose(15-3, 1) = choose(12, 1) = 12

• 或者您可以放置​​ K = 2 H(将 8 V 替换为 2 H 会失去六个点):VVHVVVVVH。这样做的方法数是 choose(15-6, 2) = choose(9, 2) = 36

• 或者您可以放置​​ K = 3 H(通过将 12 V 替换为 3 H，您失去了九个位置):HVVHHV。这样做的方法数是 choose(15-9, 3) = choose(6, 3) = 20

就是这样，您已经达到水平桩的最大数量(max K = 15/4 = 3)。然后，您只需将所有这些相加，即可得出填充这些位置的方法总数:1+ 12 + 36 + 20 = 69。

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

最终导致: