看到第n个矩形相对与第n-1个是多了一行1*2的小矩形，这个新的小矩形能如何贡献价值？
第一种情况，它直接被一个1*2的小矩形覆盖，剩余部分如何填充就是没有加新的小矩形之前的也就是和第n-1个矩形产生的结果相同
第二种情况，它的每个1*1的小矩形分别放一个1*2矩形的一半，这样就要浪费原来的一行矩形，也就是剩下n-2行，那n-2行产生的价值是已知的
那么 dp[n] = dp[n-1] + dp[n-2]； dp[0] = 0; dp[1] = 1; dp[2] = 2;
看图片一眼就知道了 n=4时
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 tmp = b; b += a; a = tmp; } return b; } };
原文：http://www.cnblogs.com/dupengcheng/p/7662421.html
