1//时间复杂度 应该是指数级
 2int fib(){
 3  if(n==0){
 4    return 0;
 5  }
 6  if(n==1){
 7    return 1;
 8  }
 9  return fib(n-1)+fib(n-2);
10}

 1// 记忆化搜索  时间复杂度O(n)
 2int memo[];
 3int fib(){
 4  if(n==0){
 5    return 0;
 6  }
 7  if(n==1){
 8    return 1;
 9  }
10  if(memo[n]==-1){
11    memo[n]=fib(n-1)+fib(n-2);
12  }
13  return memo[n];
14}

 1// 动态规划
 2int fib(int n){
 3  vector<int> memo(n+1, -1);
 4  memo[0] = 0;
 5  memo[1] = 1;
 6  for(int i=2; i<n;i++){
 7    memo[i] = memo[i-1]+memo[i-2];
 8  }
 9  return memo[n];
10}