我在一次采访中被问到这个问题我想不出一个办法，除了考虑所有的可能性，即完全的暴力。
有3种立方体1×1×1、1×2×1和1×1×2。有多少种方法可以使用上述类型的立方体生成1×2n×k维的立方体？
最佳答案
为了减少这个问题，我删除了一个常数维。
这个问题很简单：
我们有两种1*1，1*2的正方形，
有多少种方法可以做成正方形
尺寸为2^n x k，使用上述类型的正方形？
这个问题等于：
大小为2^n X k的matching中有多少Lattice graph？
因为对于每一个匹配，我们有一个模式来填充我们的正方形，边是匹配的那一组（1*2正方形），而对于另一个正方形组（1*1正方形）
我想Matching polynomial和Bipartite graph是有用的。
对于（n=1）同样的问题，可以使用递归函数来求解，并且很容易证明结果介于fibonacci_number和Catalan_number之间（有关更多详细信息，请参见this link中的fibonacci数和砖墙图案）。