Offer 10-i. Fibonacci sequence

😀 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions! 🩲 warehouse address: a daily series

Title description:

Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:

F (0) = 0, F (1) = 1, F (N) = F (N - 1) + F (N - 2), where N > 1.Copy the code

The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Example 1:

Input: n = 2 Output: 1Copy the code

Example 2:

Input: n = 5 Output: 5Copy the code

Answer:

C + + :

Dynamic programming, the dynamic programming problem is given

class Solution {
public:
    int fib(int n) {
        int j=1000000007;
        if(n==0) return 0;
        if(n==1) return 1;
        int last=1;// Modify in place to reduce memory
        int last_last=0;// Modify in place to reduce memory
        int ans;
        int m=0;
        for(int i=2; i<=n; ++i){ m=last+last_last; m=m%j;// Mod does not affect the result to prevent numbers from crossing bounds
            last_last=last;
            last=m;
        }

        returnm; }};Copy the code