Python剑指offer：矩形覆盖问题

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用8个21的小矩形
无重叠的覆盖一个28的大矩形，共有多少种方法？

* * * * * * * * * * * * * * * * * *

这个*作为一个矩形的示意图。

显然，这种大的问题我们可以分解成更小的问题，比如说，对于这个2*8的矩形放置方法f(8)而言，如果第一次竖着放，那么还剩下f(7)的放置方法需要考虑，然而，第一次，还可以横着放置，那么，还剩下的放置方法有f(6)需要考虑。因此，f(8)一共有两种模式，即f(8) = f(7) + f(6)。这是一个菲波那切数列问题，f(1)=1,f(2)=2，据此，我们可以编写程序。

class Solution:def rectangle_cover(self, number):if number == 0:returnif number == 1:return 1if number == 2:return 2if number > 2:tempArray = [1, 2]for i in range(3, number + 1):tempArray[i%2] = tempArray[0] + tempArray[1]return tempArray[number % 2]

总结

以上是生活随笔为你收集整理的Python剑指offer：矩形覆盖问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。