algorithm - 给定 3 x N 矩形，确定我们可以使用 1x3 和 3x1 瓷砖以多少种方式平铺矩形

Question

我该如何解决这个问题？我在想我试着放瓷砖，然后如果我不能再放了，我需要回溯……但我怎么知道要回溯多少？此外，在放置瓷砖后，我(代码)如何决定要填充下一个瓷砖以及使用哪种类型的瓷砖？

Answer 1

使用这个循环:F(N) = F(N - 1) + F(N - 3)
基本情况:F(0) = F(1) = F(2) = 1

这里，F(N) 表示没有一种方法可以用 3X1 或 1X3 的方 block 来平铺 3XN 网格。

• 如果您放置 3X1 方 block ，则只需求解 F(N - 1)。

• 如果你放置一个 1x3 的瓷砖，那么你不能在下面放置一个 3x1 的瓷砖它。基本上，您必须放置一组三个 1x3 的瓷砖在一起，因此你解决了 F(N - 3)。
  

求和，你得到我上面提到的重复。

希望这会有所帮助:)