作者：翟天保Steven
版權(quán)聲明：著作權(quán)歸作者所有，商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處

成都創(chuàng)新互聯(lián)成立與2013年，先為敦化等服務(wù)建站，敦化等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為敦化企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。題目描述：

我們可以用 2*1 的小矩形橫著或者豎著去覆蓋更大的矩形。請問用 n 個(gè) 2*1 的小矩形無重疊地覆蓋一個(gè) 2*n 的大矩形，從同一個(gè)方向看總共有多少種不同的方法？

數(shù)據(jù)范圍：0≤n≤38?
進(jìn)階：空間復(fù)雜度 O(1)??，時(shí)間復(fù)雜度O(n)?

注意：約定 n == 0 時(shí)，輸出 0

比如n=3時(shí)，2*3的矩形塊有3種不同的覆蓋方法(從同一個(gè)方向看)：

輸入描述：

2*1的小矩形的總個(gè)數(shù)n

返回值描述：

覆蓋一個(gè)2*n的大矩形總共有多少種不同的方法(從同一個(gè)方向看)

示例：

輸入：

4

返回值：

5

解題思路：

本題是類似青蛙跳臺(tái)階的題目，本質(zhì)上是一個(gè)數(shù)學(xué)問題。

假設(shè)2*(n)矩形的覆蓋方案數(shù)量是f(n)，則2*(n)的大矩形有兩種組合形式。2*(n-1)的大矩形加1塊豎直的矩形是一種情況，2*(n-2)的大矩形加兩塊橫放疊加的矩形是一種情況，所以f(n)=f(n-1)+f(n-2)，顯然是斐波那契數(shù)列了，用動(dòng)態(tài)規(guī)劃的解法即可。

測試代碼：

class Solution {
public:
    int rectCover(int number) {
        // 當(dāng)n為0、1、2時(shí)，可能的情況數(shù)量剛好和n一致
        if(number<= 2)
            return number;

        // 初始化
        int a = 1;
        int b = 2;
        int c = 0;

        // 斐波那契數(shù)列遍歷
        for(int i = 3; i<= number; ++i)
        {
            c = a + b;
            a = b;
            b = c;
        }

        return c;
    }
};

常規(guī)跳臺(tái)階問題可以參考：

劍指offer(C++)-JZ69：跳臺(tái)階(算法-動(dòng)態(tài)規(guī)劃)_翟天保Steven的博客-博客

該文章中提供了4種遞優(yōu)的解法，以幫助大家更好地理解動(dòng)態(tài)規(guī)劃。但該4種解法中最優(yōu)解的時(shí)間復(fù)雜度也要O(n)，因此我又探究了如何實(shí)現(xiàn)O(logn)的解法，將問題轉(zhuǎn)換為矩陣求解的形式，運(yùn)用快速冪的方法實(shí)現(xiàn)了高次冪的快速求解，達(dá)到了O(logn)水平。參考文章如下：

劍指offer(C++)-JZ10：斐波那契數(shù)列(時(shí)間復(fù)雜度O(logn)解法)_翟天保Steven的博客-博客

以上兩篇文章都是解決斐波那契數(shù)列問題的相關(guān)內(nèi)容，希望能對(duì)你有一些幫助。

---

推薦電影——消失的她！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：劍指offer(C++)-JZ70：矩形覆蓋-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://m.newbst.com/article44/hghhe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、做網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)、企業(yè)建站、品牌網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)