algorithm - 解决平铺问题

Question

我最近在比赛中遇到了这个问题:

How many ways are there to fill a 4*N board completely using only tiles of 1*4 and 4*1 dimensions?

通过很多案例，我们发现

  f(i) = f(i-1) + f(i-4) ; (i > 4)

就是这个问题的解决方案(动态规划)。但是在我们提交并获得 AC 之前，我们仍然不确定这个答案。

所以谁能解释一下如何得出上述公式，因为它对我来说并不直观。另外，如果更改了问题陈述并且我们必须使用尺寸为 2*3 和 3*2 的瓷砖，那么递归公式是什么？所以本质上我想知道如何解决此类平铺问题，方法是什么。欢迎任何好的引用链接。

谢谢

Answer 1

假设网格的宽度为 N，高度为 4。对于如何覆盖左上角的位置，您有 2 个选择:您可以用单个图 block 覆盖最左边的列，这是您的 f(i-1) 项；或者你可以覆盖前 4 列的顶行，迫使你用类似方向的瓷砖覆盖其余的列，给出 f(i-4) 项。