algorithm - 制作特定尺寸长方体的方法数量

Question

我在面试中被问到这个问题。除了考虑所有可能性之外，我想不出一种方法——即完全蛮力。

You have 3 kind of cubes 1×1×1, 1×2×1, and 1×1×2. How many ways can you make a cube of dimension 1×2ⁿ×k using the above types of cubes?

Answer 1

为了减少这个问题，我删除了一个常量维度。

this question is simple:

we have 2 kind of 1*1,1*2 Squares,

HOW MANY WAYS you can make a Square of dimension 2^n X k using the above type of Squares?

这个问题等于:多少matching在 Lattice graph大小为 2^n X k？

因为对于每一场比赛，我们都有一个模式来填充我们的广场，即边缘匹配的集合(1*2 广场)。对于其他广场集(1*1 广场)

我猜Matching polynomial & Bipartite graph很有用。

同题(n=1)可以用递归函数求解，很容易证明结果在fibonacci_number之间。和 Catalan_number (有关更多详细信息，请参阅 this link 中的斐波那契数和砖墙模式)