, this is the second time blogger brush this subject classic topic of classic algorithms, the Fibonacci sequence can use recursion to solve, but if demand a larger number of cases, there will be a double counting problem, complexity is higher, so we in the use of recursion method, greatly reduces the time and space complexity.

Topic describes

Their thinking

  • If the target value is less than or equal to 1, it returns directly.
  • If the target value is greater than or equal to 1, define two temporary variables to hold the first two numbers.
  • The final solution can be obtained by updating the two values in a loop.

AC code

Since we need to do the mod calculation in Leetcode, we just need to mod the result.

var fib = function (n) {
    if (n <= 1) return n;

    let prev1 = 1;
    let prev2 = 0;
    let result = 0;

    for (let i = 2; i <= n; i++) {
        result = (prev1 + prev2) % 1000000007;
        prev2 = prev1;
        prev1 = result;
    }
    return result;
};
Copy the code

The title to reflect

  • Learn to use non-recursive methods to solve Fibonacci sequences to reduce the complexity of the algorithm.