leetcode 506 斐波那契数

一、问题描述

二、解题思路

（1）解法一：直接递归

按照题目意思，直接暴力递归，这种方法重复计算太多。

（2）解法二：记忆化搜索

由于解法一重复计算太多，比如在计算fib(5)的时候需要计算fib(3)和fib(4)，在计算fib(4)的时候也要计算fib(3)，重复计算过多。

我们可以用一个数组，将前面计算过的结果存储起来，如果需要的结果是前面计算过的，就直接使用即可。

（3）解法三：动态规划

由于fib(n)=fib(n-2)+fib(n-1)，所以，可以开辟一个数组dp来存放相应的斐波那契数值，dp[i]的值为fib(i)的值。

（4）解法四：滚动数组

由于fib(n)只与fib(n-1)与fib(n-2)有关，所以只需要保存前面的两个数即可。

三、代码实现

解法一：直接递归

class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        return fib(n-1)+fib(n-2);
    }
};

解法二：记忆化搜索

class Solution {
    vector<int> memo;
public:
    int fib(int n) {
        //边界处理
        if(n==0) return 0;
        if(n==1) return 1;
        
        memo.resize(n+1,-1);
        memo[0]=0;
        memo[1]=1;
        return dfs(n);
    }

    int dfs(int n){
        //如果memo中有，直接返回
        if(memo[n]!=-1) return memo[n];
        //如果memo中没有，则存入memo
        else{
            memo[n]=dfs(n-2)+dfs(n-1);
            return memo[n];
        }
    }
};

解法三：动态规划

class Solution {
public:
    int fib(int n) {
        //边界处理
        if(n==0) return 0;
        if(n==1) return 1;

        //填写dp数组
        vector<int> dp(n+1,0);
        dp[0]=0;dp[1]=1;
        for(int i=2;i<=n;i++) 
            dp[i]=dp[i-1]+dp[i-2];

        return dp[n];
    }
};

解法四：滚动数组

class Solution {
public:
    int fib(int n) {
        //边界处理
        if(n==0) return 0;
        if(n==1) return 1;
        
        int a,b,c;
        a=0;b=1;
        for(int i=2;i<=n;i++) {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};

原文地址：https://blog.csdn.net/2301_80296866/article/details/152952648

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！