首页 > 代码库 > 很好的矩阵覆盖问题

很好的矩阵覆盖问题

参考这篇文章:

http://www.cnblogs.com/CheeseZH/p/5112946.html

 

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
 
class Solution {
public:
    int rectCover(int n) {
        if (n == 1 || n == 2) return n;
        int a = 1, b = 1;
        while (n-- >= 2) {
            a = a + b;
            b = a - b;
        }
        return a;
    }
};

开始看,很难懂是吧,我也看了好一会儿。

把 b = a - b 用上一个式子a = a + b代入,得到,其实 b = a + b - b = a,其实就是b存储了上一个a。

这样就能够看出来,a和b分别存储了上一个结果和上上一个结果。再结合DP的思想,

最终的结果,其实就是竖过来放一个的结果(对应上一个结果)+横过来放两个的结果(对应上上一个结果)。

很巧妙是吧。

 

很好的矩阵覆盖问题