斐波那契数列的几种写法 2021-02-23

1. //递归写法
2. #include<stdio.h>
3. int feibo(int n)
4. {
5.  if(n==1) return 0;
6.  else if(n<=3) return 1;
7.  else return feibo(n-1)+feibo(n-2); 
8. }
9. int main()
10. {
11.   int a;
12.   scanf("%d",&a);
13.   printf("%d\n",feibo(a));
14.   return 0;
15.  }

1. //备忘录递归  解决重叠问题
2. #include <iostream>
3. #include <vector>
4. using namespace std;
5. int helper(vector<int> &memo,int n);
6. int fib(int n){
7.  if(n==0)return 0;
8.  vector<int> memo(n+1,0);
9.  return helper(memo,n);
10. }
11. int helper(vector<int> &memo,int n){
12.   if(n==1)return 0;
13.   if(n==2)return 1;
14.   if(memo[n]!=0) return memo[n];
15.   memo[n]=helper(memo,n-1)+helper(memo,n-2);
16.   return memo[n];
17. }
18. int main()
19. {
20.   int n;
21.   cin>>n;
22.   cout<<fib(n)<<endl;
23.   return 0;
24. }

1. //dp数组迭代
2. #include <iostream>
3. #include <vector>
4. using namespace std;
5. int fib(int n){
6.  if(n==1)return 0;
7.  if(n==2)return 1;
8.  vector<int> dp(n+1,0);
9.  dp[1]=0;
10.   dp[2]=1;
11.   for(int i=3;i<=n;i++)
12.     dp[i]=dp[i-1]+dp[i-2];
13.   return dp[n];
14. }
15. int main()
16. {
17.   int n;
18.   cin>>n;
19.   cout<<fib(n)<<endl;
20.   return 0;
21. }

1. //状态压缩
2. #include <iostream>
3. using namespace std;
4. int fib(int n){
5.  if(n==1)return 0;
6.  if(n==2)return 1;
7.  int prev=0,curr=1;
8.  for(int i=3;i<=n;i++){
9.    int sum=prev+curr;
10.     prev=curr;
11.     curr=sum;
12.   }
13.   return curr;
14. }
15. int main()
16. {
17.   int n;
18.   cin>>n;
19.   cout<<fib(n)<<endl;
20.   return 0;
21. }