天天看點

劍指offer之矩形覆寫問題問題描述求解思路AC代碼斐波那契數列遞推思想總結

問題描述

我們可以用 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;
    }
};
           

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

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

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

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