class Solution {
public:
    int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int n1 = 1, n2 = 1, n3;
        for (int i = 3; i <= n; ++i) {
            n3 = n1 + n2;
            n1 = n2;
            n2 = n3;
        }
        return n3;
    }
};

递推就行了