题解 | #矩形覆盖#

class Solution {
public:
    int rectCover(int number) {
        /**
         * f(1) = 1
         * f(2) = 2
         * f(3) = 3
         * f(4) = f(3) + f(2)
         */
        if (number == 0) return 0;
        if (number == 1) return 1;
        if (number == 2) return 2;

        int f1 = 1;
        int f2 = 2;
        int f3;
        for (int i = 3; i <= number; ++i) {
            f3 = f1 +f2;

            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
};

这道题的难点在于归纳总结

首先，像动态规划这种算法是有一定的规律可寻的

你一定要找得到 高中 “数学归纳法” 中的递推公式， 不然没法用动态规划算法求解的；

斐波那契数列求第n项的数值就是一个很好的例子：

我们通过斐波那契的数列找到了规律：

f(1) = 1

f(2) = 1;

f(3) = f(1) + f(2)

f(4) = f(2) + f(3)

....

f(n) = f(n-1) + f(n-2)

....