0（4.5 x 1 块）和 9（3 x 1 块）--> 9 C 0 = 1 种方式
1 种方式 + 35 种方式 + 28 种方式 + 1 种方式 = 65 种方式
如您所见，这里的方式数量远远不及 7958。我在这里做错了什么？
还有，我该如何找到构建一个 48 x 10 面板的方式数量？因为手动计算 7958 种方式有点困难。
如何编写程序来计算 7958 面板的方式数量？构建一个程序来计算结果会更容易吗？任何帮助都将不胜感激。
|=1行，2 - =1列）：+---------------------------+
| | | | |
| | | | |
| | | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
在这里，我们可以看到有4种不同的基本行类型，但是它们都不是有效的面板（它们都违反了“块不能对齐”的规则）。但是我们可以使用这些行类型来创建多个面板：
+---------------------------+
| | | | |
| | | | |
| | | |
+---------------------------+
+---------------------------+
| | | | |
| | | | |
| | | |
+---------------------------+
+---------------------------+
| | | | |
| | | | |
| | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
...
+---------------------------+
| | | | |
| | | |
| | | | |
+---------------------------+
+---------------------------+
| | | |
| | | | |
| | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
+---------------------------+
| | | |
| | | |
| | | |
+---------------------------+
实际上有四个，但在这种情况下，它只是巧合与使用“选择”功能得到的结果相匹配。就总面板配置而言，远不止四个。
(3 3 3 3)，(4.5 4.5 3)，(4.5 3 4.5)，(3 4.5 4.5)。我会将它们表示为间隙列表。例如：(3 6 9)，(4.5 9)，(4.5 7.5)，(3 7.5)。例如：
a. 在(3 6 9)上适合(4.5 7.5)。
b. 在(4.5 9)上适合(3 7.5)。
c. 在(4.5 7.5)上适合(3 6 9)。
d. 在(3 7.5)上适合(4.5 9)。
步骤2中的规则转换为可能邻居的数组。数组的每个元素对应于一个行类型，并保存该行类型可能相邻的行类型的索引。
0: (2)
1: (3)
2: (0)
3: (1)
1 1 1 1
接下来的一行是通过为每种行类型添加可能的相邻行在前一行上形成的方式数量来形成的。对于宽度为12的情况，结果再次是1 1 1 1。最后，只需将最后一行相加即可。
复杂度:
找到行类型对应于枚举树的叶子节点;这棵树有大约(/ width 3)层，因此这需要O(2w/3) = O(2w)的时间。
检查两个行类型是否适合需要花费与它们的长度成比例的时间，O(w/3)。建立交叉表与行类型的数量的平方成比例。这使得第二步为O(w/3·22w/3) = O(2w)。
动态规划需要行数乘以行类型的数量乘以平均相邻数（我估计与行类型的对数成正比），O(h·2w/3·w/3) = O(2w)。
正如您所看到的，这全部都被行类型的数量所主导，而这些随着宽度的增加呈指数增长。幸运的是，常数因子相当低，因此48×10可以在几秒钟内解决。
这看起来像是一种可以通过递归解决的问题。以下是一个算法的简要概述，其中包含一个接受前一层和剩余层数作为参数的递归方法：
我们的想法是构建所有可能的有效层的组合。一旦我们在27x5的示例中有了5个有效层叠加在一起，我们就构建了一个完整的有效面板。因此，算法应该找到（并因此计算）每个可能的有效面板，确保只计算一次。
这里是Java的解决方案，数组长度检查等有些凌乱，但我相信你可以轻松地优化它。
无论如何，我希望这能帮助你展示算法的工作原理 :-)
import java.util.Arrays;
public class Puzzle
{
// Initial solve call
public static int solve(int width, int height)
{
// Double the widths so we can use integers (6x1 and 9x1)
int[] prev = {-1}; // Make sure we don't get any collisions on the first layer
return solve(prev, new int[0], width * 2, height);
}
// Build the current layer recursively given the previous layer and the current layer
private static int solve(int[] prev, int[] current, int width, int remaining)
{
// Check whether we have a valid frame
if(remaining == 0)
return 1;
if(current.length > 0)
{
// Check for overflows
if(current[current.length - 1] > width)
return 0;
// Check for aligned gaps
for(int i = 0; i < prev.length; i++)
if(prev[i] < width)
if(current[current.length - 1] == prev[i])
return 0;
// If we have a complete valid layer
if(current[current.length - 1] == width)
return solve(current, new int[0], width, remaining - 1);
}
// Try adding a 6x1
int total = 0;
int[] newCurrent = Arrays.copyOf(current, current.length + 1);
if(current.length > 0)
newCurrent[newCurrent.length - 1] = current[current.length - 1] + 6;
else
newCurrent[0] = 6;
total += solve(prev, newCurrent, width, remaining);
// Try adding a 9x1
if(current.length > 0)
newCurrent[newCurrent.length - 1] = current[current.length - 1] + 9;
else
newCurrent[0] = 9;
total += solve(prev, newCurrent, width, remaining);
return total;
}
// Main method
public static void main(String[] args)
{
// e.g. 27x5, outputs 7958
System.out.println(Puzzle.solve(27, 5));
}
}