class Solution {
public:
    // 注意要求空间复杂度是O(1) 所以不能用vector来做了
    // 先试试dp
    int Fibonacci(int n) {

        if(n<3)
            return 1;
        int dp1 = 1;
        int dp2 = 1;
        int tmp = 0;
        for(int i=3; i<=n; ++i)
        {
            tmp = dp1 + dp2; // 递推

            dp1 = dp2;

            dp2 = tmp;
        }

        return tmp;



    }
};

自己：不借用数组 因为转移公式里之和两项有关 时间复杂度O(n)