劍指offer之矩形覆寫問題

問題描述

我們可以用 2 × 1 2\times 1 2×1的小矩形橫着或者豎着去覆寫更大的矩形。請問用n個 2 × 1 2\times 1 2×1的小矩形無重疊地覆寫一個 2 × n 2\times n 2×n的大矩形，總共有多少種方法？

求解思路

同樣是斐波那契的數列的思路，本質上是動态規劃。

• n<=0時，結果為零，這是下界條件。
• n==1時，隻有豎着一種覆寫方式。
• n==2時，有并排橫着和并排豎着兩種方式。
• 假設n步的情況下有 f ( n ) f(n) f(n)種方式，那麼如果前一個狀态是隻差了一個豎着的2*1矩形，那麼為 f ( n − 1 ) f(n-1) f(n−1)；如果是差了兩個矩形的空間，那麼是 f ( n − 2 ) f(n-2) f(n−2)；綜上可知： f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)

之後就是利用遞推求解了。。。。

AC代碼

class Solution {
  public:
    int rectCover(int number) {
        if(number <= 0) {
            return 0;
        }
        if(number == 1) {
            return 1;
        }
        if(number == 2) {
            return 2;
        }
        int a = 1, b = 2;
        for(int i = 3; i <= number; ++i) {
            int t = a;
            a = b;
            b = t + a;
        }
        return b;
    }
};
           

斐波那契數列遞推思想總結

本質上，斐波那契遞推思想就是一個動态規劃。利用前面的計算結果，遞推地計算後邊的，可以有效的防止重複的運算。一般這種問題的解決步驟如下：

• 先找出幾個容易計算的初始條件
• 尋找最少的初始條件的組合方式，使之可以遞推出後面的結果
• 尋找一般的遞推公式

可能尋找公式的時候，需要自己進行簡化，比如前面的變态跳台階問題。但是，核心的步驟還是找公式！！！