一：解题思路
方法一：递归法，Time：O(2^n),Space:O(n)
方法二：迭代法一：Time:O(n),Space:O(n)
方法三：迭代法二：Time：O(n),Space:O(1)
二：完整代码示例 (C++版和Java版)
方法一C++:
class Solution { public: int fib(int N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N-2); } };
方法一Java：
class Solution { public int fib(int N) { if(N==0) return 0; if(N==1) return 1; return fib(N-1)+fib(N-2); } }
方法二C++:
class Solution { public: int fib(int N) { if (N == 0) return 0; if (N == 1) return 1; vector<int> d(N,0); d[0] = 0; d[1] = 1; for (int i = 2; i < N; i++) { d[i] = d[i - 1] + d[i - 2]; } return d[N-1]; } };
方法二Java：
class Solution { public int fib(int N) { if(N==0) return 0; if(N==1) return 1; int[] d=new int[N+1]; d[0]=0; d[1]=1; for(int i=2;i<N+1;i++) { d[i]=d[i-1]+d[i-2]; } return d[N]; } }
方法三C++:
class Solution { public: int fib(int N) { if (N == 0) return 0; if (N == 1) return 1; int first = 0; int second = 1; for (int i = 2; i < N + 1; i++) { int cur = first + second; first=second; second = cur; } return second; } };
方法三Java:
class Solution { public int fib(int N) { if(N==0) return 0; if(N==1) return 1; int first=0; int second=1; for(int i=2;i<N+1;i++) { int cur=first+second; first=second; second=cur; } return second; } }
原文：https://www.cnblogs.com/repinkply/p/12517111.html