問題描述
我們可以用 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;
}
};
斐波那契數列遞推思想總結
本質上,斐波那契遞推思想就是一個動态規劃。利用前面的計算結果,遞推地計算後邊的,可以有效的防止重複的運算。一般這種問題的解決步驟如下:
- 先找出幾個容易計算的初始條件
- 尋找最少的初始條件的組合方式,使之可以遞推出後面的結果
- 尋找一般的遞推公式
可能尋找公式的時候,需要自己進行簡化,比如前面的變态跳台階問題。但是,核心的步驟還是找公式!!!