C++题解 | #矩形覆盖#

此题显然与斐波那契数列不能说毫不相干，只能是一模一样。以 的矩形为例，其可以在左端竖着填充一个 的小矩形，之后便剩下 的大小，也可在左上端横着填充一个小矩形，那么左下端很显然也必须横着填充一个，即只剩下 的矩形待填充。故而可知,故而，等同于斐波那契数列。则

class Solution {
public:
    int rectCover(int number) {
        int q1 = 1, q2 = 1, ans;
        if (number == 0)
            return 0;
        else if (number == 1)
            return q1;
        number = number - 1;
        while (number--) {
            ans = q1 + q2;
            q1 = q2;
            q2 = ans;
        }
        return ans;
    }
};