It is

There is a sequence called the Fibonacci sequence that satisfies this condition:

  • The 0th term is 0, and the first term is 1
  • Every term after that is the sum of the first two terms

Evaluate the NTH term

Solving method

  • recursive

    • If you solve for the 0th term or the first term, you just return it
    • If you solve for the NTH term, you return the n-1 term plus the n-2 term
class Solution { public int fib(int n) { if(n == 0 || n ==1){ return n; } return fib(n - 1) + fib(n - 2); }}Copy the code

  • The iteration

Take the 0th term and go to the NTH term, save the first two terms in temporary variables.

class Solution { public int fib(int n) { if(n == 0 || n == 1){ return n; } int fib0 = 0; int fib1 = 1; int tmp = 0; for(int i = 2; i <= n; i++){ tmp = fib0; fib0 = fib1; fib1 = (fib0 + tmp)%(1000000007); } return fib1; }}Copy the code

  • Dynamic programming

Take an array of length n + 1, same as the previous iteration, and return dp[n].

class Solution { public int fib(int n) { int[] dp = new int[n + 1]; for(int i = 0 ; i <= n; i++){ if(i == 0 || i == 1){ dp[i] = i; }else{ dp[i] = (dp[i - 1] + dp[i - 2]) % (1000000007); } } return dp[n]; }}Copy the code

  • Matrix rapid power

I myself is no matter how can not think of such a solution, a little understand some

The first formula, which can be verified by simple matrix multiplication at each position, is a mixture of the matrix multiplication form f(n) = f(n-1) + f(n-2)

We’re just complicating the problem with this first expression, we’re not reducing the complexity of time, but it’s paving the way for the decomposition of powers

A isThe solution to the NTH power can be converted to (a^(n/2))^2. Note the subtle difference between odd and even numbers. This idea is easy to implement recursively

class Solution { public int fib(int n) { if(n == 0 || n == 1){ return n; } long[][] last = getMatrixAt(n - 1); return (int)last[0][0]; } public long[][] getMatrixAt(int n){ long[][] orign = new long[2][2]; orign[0][0] = 1; orign[0][1] = 1; orign[1][0] = 1; orign[1][1] = 0; long[][] last; if(n == 1){ last = orign; }else if( n % 2 == 0){ last = matrixMul(getMatrixAt(n/2),getMatrixAt(n/2)); }else{ last = matrixMul( matrixMul(getMatrixAt((n - 1)/2),getMatrixAt((n - 1)/2) ),orign); } return last; } public long[][] matrixMul(long[][] matrix1,long[][] matrix2){ long[][] matrix = new long [2][2]; matrix[0][0] = ((matrix1[0][0] * matrix2[0][0])% (1000000007) + (matrix1[0][1] * matrix2[1][0]) % (1000000007)) % (1000000007); matrix[0][1] = ((matrix1[0][0] * matrix2[0][1])% (1000000007) + (matrix1[0][1] * matrix2[1][1]) % (1000000007)) % (1000000007); matrix[1][0] = ((matrix1[1][0] * matrix2[0][0])% (1000000007) + (matrix1[1][1] * matrix2[1][0]) % (1000000007)) % (1000000007); matrix[1][1] = ((matrix1[1][0] * matrix2[0][1])% (1000000007) + (matrix1[1][1] * matrix2[1][1]) % (1000000007)) % (1000000007); return matrix; }}Copy the code

Time complexity analysis

  • Direct recursion is the slowest of the four, and the expansion is a binary tree, order n^2.
  • The direct iteration is O(n), all the way through
  • Dynamic programming is also O(n), but requires more space than direct iteration
  • Matrix fast power is the fastest, up to O(logn), is continuously divided to n==2 matrix