计算机科学基础leetcode刷题动态规划
Source
Edit
History

斐波那契数列

Problem: LCR 126. 斐波那契数

解题方法

  • dp数组含义,dp[i]就是表示f(i)的斐波那契数的值a

  • 递推公式: dp[i] = dp[ i- 1] + dp[ i - 2]

  • 初始化: dp[0]= 0; dp[1] = 1;

  • 递推顺序:顺序

  • 不要忘记对结果取模1000000007

  • 可以压缩,因为只取决于前两个状态

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {

public:

    int fib(int n) {

        if (n < 1)

            return 0;

        if (n < 2)

            return 1;

        vector<int> dp(n + 1, 0);

        dp[0] = 0;

        dp[1] = 1;

        // for (int i = 2; i < n + 1; i++) {

        //     dp[i] = dp[i - 1] + dp[i - 2];

        //     dp[i] = dp[i] % 1000000007;

        // }

        int sum;

        for (int i = 2; i < n + 1; i++) {

            sum = (dp[0]  + dp[1]) % 1000000007;

            dp[0] = dp[1];

            dp[1] = sum;

        }

        return sum;

    }

};