NO7斐波那契数列

用递归的写法，复杂度将是O(2^n)级别的，无法忍受。 用三个变量存储递归的中间值，时间复杂度能到O(n)。

    public int Fibonacci (int n) {
        // write code here
       int t1 = 1;
       int t2 = 1;
       int t3 = 1;
       for(int i = 2; i < n; i++){
            t3 = t1 + t2;
            t1 = t2;
            t2 = t3;
       }
       return t3;
    }

NO8跳台阶

递归做法

class Solution {
public:
    int jumpFloor(int number) {
        // write code here
        if(number == 1) return 1;
        if(number == 2) return 2;
        return jumpFloor(number -1) + jumpFloor(number - 2);
    }
};

简单dp做法

class Solution {
public:
    int jumpFloor(int number) {
        // write code here
        std::array<int, 50> dp{};
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= number; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
​
        return dp[number];
    }
};

NO9跳台阶扩展

dp，找规律：dp[i] = 2 * dp[i-1];

第i次跳，可以是第i-1次的数目+1跳，也可以是第i-2次的数目+2跳，也可以是第i-3次的数目+3跳，即：

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + … + dp[0] dp[i-1] = dp[i-2] + dp[i-3] + … + dp[0] 所以，dp[i] = 2 * dp[i-1];

    int jumpFloorII(int number) {
        // write code here
        std::array<int, 50> dp{};
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=number; i++){
            dp[i] = 2*dp[i-1];
        }
        return dp[number];

NO10矩形覆盖

找规律？类似斐波那契数列

class Solution {
public:
    int rectCover(int number) {
        if(number <= 2) 
            return number;
        int dpi_2 = 1; 
        int dpi_1 = 2; 
        int res = 0;
        for(int i = 3; i <= number; i++){
            //公式相加
            res = dpi_1 + dpi_2; 
            //变量更新
            dpi_2 = dpi_1; 
            dpi_1 = res;
        }
        return res;
    }
};

PS：感觉以后遇到简单的dp问题，想不出来转移方程可以先多写几个找规律？