递归
class Solution { public: int Fibonacci(int n) { if (n == 1 || n == 2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } };
空间压缩
class Solution { public: int Fibonacci(int n) { if (n == 1 || n == 2) return 1; int a1 = 1; int a2 = 1; int a3 = 0; for (int i = 3; i <= n; ++i) { a3 = a1 + a2; a1 = a2; a2 = a3; } return a3; } };