【演算法入門09】矩形覆寫

核心考點：場景轉化成模型，特殊情況分析，簡單dp

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

例如，n=3時， 2 × 3 2\times3 2×3 的矩形塊有3種覆寫方法（從同一個方向看）：

決議：
對于這道題，我們若是從無到有一個個的放小矩形的話，那么我們遲早會崩潰，因為當我們才放到4個小矩形的時候情況就已經很多了，

這時我們可以嘗試從后往前進行分析，尋找規律，

我們將 f ( x ) f(x) f(x)定義為用 2 × 1 2\times1 2×1 的小矩形無重疊地覆寫一個 2 × x 2\times x 2×x 的大矩形的覆寫總方法數，那么就有如下結論：

情況一： 覆寫一個 2 × n 2\times n 2×n 的大矩形，若最后一個小矩形已經確定是豎著放的，那么覆寫該大矩形的覆寫總方法數就等于覆寫 2 × ( n ? 1 ) 2\times (n-1) 2×(n?1) 的大矩形的覆寫總方法數，

情況二： 覆寫一個 2 × n 2\times n 2×n 的大矩形，若最后一個小矩形已經確定是橫著放的，那么覆寫該大矩形的覆寫總方法數就等于覆寫 2 × ( n ? 2 ) 2\times (n-2) 2×(n?2) 的大矩形的覆寫總方法數，

而實際覆寫 2 × n 2\times n 2×n 的大矩形時，我們并不知道最后一個小矩形是橫著放還是豎著放，所以覆寫 2 × n 2\times n 2×n 的大矩形的覆寫總方法數應該是這兩種情況的方法數之和，即 f ( n ) = f ( n ? 1 ) + f ( n ? 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n?1)+f(n?2)，

當然，我們不能讓這個公式一直往前推，總得給它一個盡頭，很容易知道的就是 f ( 1 ) f(1) f(1)和 f ( 2 ) f(2) f(2)，

f ( 1 ) f(1) f(1)就是用 2 × 1 2\times1 2×1 的小矩形無重疊地覆寫一個 2 × 1 2\times 1 2×1 的大矩形的覆寫總方法數，很明顯只有一種覆寫方法，

f ( 2 ) f(2) f(2)就是用 2 × 1 2\times1 2×1 的小矩形無重疊地覆寫一個 2 × 2 2\times2 2×2 的大矩形的覆寫總方法數，很明顯這時有兩種覆寫方法，

也就是說， f ( 1 ) = 1 f(1)=1 f(1)=1， f ( 2 ) = 2 f(2)=2 f(2)=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)這個公式時，就應該知道這實際上就是一個斐波那契數列，我們直接使用斐波那契數列的最優解決方案進行代碼撰寫即可，

//動規
class Solution {
public:
	int rectCover(int number) {
		if (number == 1 || number == 2) //f(1)=1, f(2)=2
			return number;
		int first = 1; //f(1)=1
		int second = 2; //f(2)=2
		int third = 0;
		while (number > 2) //進行number-2次計算
		{
			//f(n)=f(n-1)+f(n-2)
			third = first + second;
			first = second;
			second = third;
			number--;
		}
		return third;
	}
};