给定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瓦片平铺3XN网格的方法.

• 如果你放置一个3X1瓷砖,那么你只需要解决F(N - 1).

• 如果你放置1x3瓷砖,那么你就不能在它下面放一个3x1瓷砖.基本上,你必须将一组三个1x3瓷砖放在一起,因此你可以解决F(N - 3).
  

拿出总和,你得到我上面提到的复发.

希望这可以帮助 :)