矩形覆盖（斐波那契）

其实找规律可以发现它就是一个斐波那契数列，可以采用递归和非递归的方式写。

对于n=4的情况，我们先看左边第一块怎么放，有两种方式，第一种竖着放，剩下3*2的位置，剩下的位置就是n=3的结果，第二种就是横着放，因为是横着放其下面的区域也就只能也放一块横着的，剩下的位置就是n=2的结果；
所以可以看出f[ n ] = f[ n-1]+f[ n-2 ] ;
1.非递归

class Solution {
public:
    int rectCover(int number) {
        int f[number+1];
        f[0] = 0;
        f[1] = 1; f[2] = 2;
        for(int i=3;i<=number;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[number];
    }
};

2.递归

class Solution {
public:
    int rectCover(int number) {
        int f[number+1];
        f[0] = 0;
        f[1] = 1; f[2] = 2;
        for(int i=3;i<=number;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[number];
    }
};

递归写的时间居然更短。

本文地址：https://blog.csdn.net/qq_43811879/article/details/110291766