您可以製作特定尺寸的長方體的方式數量

Question

我在面試中被問到這個問題。除了採取所有可能性，我無法想出一個辦法 - 即完全暴力。

您有3種立方體1×1×1,1×2×1和1×1×2。使用上述類型的立方體，可以用多少種方法制作一個尺寸爲1×2 ⁿ×k的立方體？

Answer 1

爲了減少這個問題，我刪除了一個常量維。

這個問題很簡單：

我們2種1個* 1,1 * 2個格，

多少種方式可以使尺寸2^N X的廣場 k使用上述類型的正方形？

和這個問題通過平等： 多少matching在Lattice graph與2^n的值X k大小？

，因爲每場比賽，我們有一個模式來填補我們的廣場，是集（1×2平方），其中邊緣是其他方組（1×1坊）

match.and我猜Matching polynomial & Bipartite graph很有用。

與同樣的問題

（N = 1），可以使用遞歸函數來解決it.and很容易證明，結果是fibonacci_number和Catalan_number之間（詳細內容見斐波那契數和磚牆格局this link）