解题思路

斐波那契数列为前两项的和，第0项和第1项分别为0， 1.

f(0) = 0 f(1) = 1 f(2) = f(0) + f(1) = 1 f(3) = f(2) + f(1) = 3

下标从2开始，从前往后遍历

f[n] = f[n - 1] + f[n - 2]

代码

Python

1
2
3
4
5
6
7
8
9
10
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: return n
        MOD = 10 ** 9 + 7
        fib = [0 for _ in range(n + 1)]
        fib[1] = 1
        for i in range(2, n + 1):
            fib[i] = fib[i - 1] + fib[i - 2]
        return fib[-1] % MOD

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int fib(int n) {
        const int N = 1e9 + 7;
        if (n <= 1) return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        for (int i = 2; i < n + 1; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= N;
        }
        return dp[n];
    }
};

GO

func fib(n int) int {
    if n <= 1 {return n}
    MOD := 1000000007
    dp := make([]int, n + 1, n + 1)
    dp[1] = 1
    for i := 2; i < n + 1; i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= MOD
    }
    return dp[n]
}