我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用8個(gè)21的小矩形
無重疊的覆蓋一個(gè)28的大矩形，共有多少種方法？

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

這個(gè)*作為一個(gè)矩形的示意圖。

顯然，這種大的問題我們可以分解成更小的問題，比如說，對于這個(gè)2*8的矩形放置方法f(8)而言，如果第一次豎著放，那么還剩下f(7)的放置方法需要考慮，然而，第一次，還可以橫著放置，那么，還剩下的放置方法有f(6)需要考慮。因此，f(8)一共有兩種模式，即f(8) = f(7) + f(6)。這是一個(gè)菲波那切數(shù)列問題，f(1)=1,f(2)=2，據(jù)此，我們可以編寫程序。

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]

總結(jié)

以上是生活随笔為你收集整理的Python剑指offer：矩形覆盖问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。