当前位置：
  1. 首页
  2. 剑指offer刷题第七期
  3. 问题详情

【杂题】剑指 Offer 10- I. 斐波那契数列

本问题对应课程链接：剑指offer刷题第七期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
78 5

共以下 5 个回答

  • 陆狗陆狗 普通 2025年1月3日 下午9:33

    解题思路
    – 常规dp的思想，主要是要学会大数取模的表达式
    【题解1】

    class Solution {
    public int fib(int n) {

        // 主要是大数取模， (x+y)取p= (x取p+y取p)取p
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        int p = 1000000007;
        for (int i = 2; i <= n; i++) {
            // 【错误】公式写错了，写成了(dp[i - 1] % p) + (dp[i - 2] % p) % p;
            dp[i] = (dp[i - 1] % p + dp[i - 2] % p) % p;
        }
        return dp[n];
    }
}
- 错误点1：公式写错了，写成了(dp[i - 1] % p) + (dp[i - 2] % p) % p;

【题解2】优化了一下取模，因为dp[i]一定是取模放进去的，所以dp[i]%p=dp[i]
class Solution {
    public int fib(int n) {

        // 主要是大数取模， (x+y)取p= (x取p+y取p)取p
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        int p = 1000000007;
        for (int i = 2; i <= n; i++) {
            // 【优化】因为dp[i]一定是取模放进去的，所以dp[i]%p=dp[i]
            dp[i] = (dp[i - 1]+ dp[i - 2]) % p;
        }
        return dp[n];
    }
}
【题解3】优化了变量，其实最后只需要3个变量即可
class Solution {
    public int fib(int n) {

        // 主要是大数取模， (x+y)取p= (x取p+y取p)取p
        if (n <= 1) {
            return n;
        }

        int a = 0;
        int b = 1;
        int c = 0;
        int p = 1000000007;
        for (int i = 2; i <= n; i++) {
            c = (a + b) % p;
            a = b;
            b = c;
        }
        return c;
    }
}
    0 赞同 0 条回复
  • 秋山丽奈 普通 2024年12月30日 下午8:09

    思路： 递归+记忆化

    class Solution {

    HashMap<Integer, Integer> memo = new HashMap<>();

    public int fib(int n) {
        if(n <= 0){
            return 0;
        }

        if(n == 1){
            return 1;
        }

        if( this.memo.getOrDefault(n, -1) != -1){
            return this.memo.get(n);
        }

        int temp = (fib(n-1) + fib(n-2)) % 1000000007;;
        this.memo.put(n, temp);

        return temp;

    }
}
    0 赞同 0 条回复
  • Aatorx 永久会员 2024年12月27日 下午3:58 
    class Solution {
public:
    int fib(int n) {
        int a = 0;
        int b = 1;
        if(n <= 1) return n;
        for (int i = 1; i < n; i++) {
            int c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return b;
    }
};

    时间复杂度O(N)，空间复杂度O(1)。

    0 赞同 0 条回复
  • 晓宇 普通 2024年12月26日 下午5:43 
    class Solution {
public:
    // 递归
    int fib(int n) {
        if(n <= 2){
            if(n == 0) return 0;
            else return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }
    // o(2^n) o(n)
};

class Solution {
public:
    // 递归 剪枝优化 记忆化搜索
    int fib(int n){
        std::vector<int> arr(101, -1);
        return __fib(n,arr);
    }

    int __fib(int n, vector<int> &arr) {
        if(n <= 2){
            if(n == 0) return 0;
            else return 1;
        }
        // 剪枝优化
        if(arr[n] != -1)  return arr[n];
        int sum = (__fib(n - 1,arr) + __fib(n - 2,arr)) %  1000000007;
        arr[n] = sum;
        return sum;
    }
    // o(n) o(n)栈空间递归n次
};

class Solution {
public:
    // 递归 自底向上
    int fib(int n){
        if(n <= 1) return n;

        int ans;
        int pre_ans = 1;
        int ppre_ans = 0;
        for(int i = 2;i <= n;i++){
            ans = (pre_ans + ppre_ans) % 1000000007;
            ppre_ans = pre_ans;
            pre_ans = ans;
        }
        return ans;
    }

    // o(n) o(1)
};
    0 赞同 0 条回复
  • Xiang. 永久会员 2024年12月26日 上午11:55 
    class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int i=0;
        int j=1;
        int sum=0;
        for(int k=2;k<=n;k++){
            sum=(i+j)% 1000000007;
            i=j;
            j=sum;
        }
        return sum;
    }
}
时间复杂度：O（n）
空间复杂度：O（1）
    0 赞同 0 条回复

# 回答此问题

后才能回答