This is the first day of my participation in the August Challenge. For details, see:August is more challenging

JZ7 Fibonacci series

describe

You know the Fibonacci sequence, now you want to input an integer n, you output the NTH term of the Fibonacci sequence (starting from 0, the 0th term is 0, the first term is 1). N 39 or less

Example 1

Enter: 4. Return: 3Copy the code

The problem solving

1. Array of for loops

After processing the critical values, an array is created and the NTH value is computed in the for loop according to the Fibonacci sequence recurrence formula

This is a little bit like dynamic programming

/** * Runtime: 12ms * > 79.52% Submitted by more than 5.00% in Java code 9720 KB * * < p > * code concision @ param n * * * @ return * / public static int the Fibonacci (int n) {if (n = = 0 | | n  == 1) { return n; } int[] array = new int[n + 1]; array[0] = 0; array[1] = 1; for (int i = 2; i <= n; i++) { array[i] = array[i - 1] + array[i - 2]; } return array[n]; }Copy the code

2. Simple recursion

Handle the critical value, invoke the method recursively according to the formula

/** * / / / /** * / / / / /** * / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / Public static int Fibonacci1(int n) {if (n) {if (n)  == 0 || n == 1) { return n; } return Fibonacci1(n-1) + Fibonacci1(n-2); }Copy the code

3. Memo algorithm

Use map as the cache to reduce double counting of sequence items

/** * <p> <p style = "box-sizing: border-box; @param n * @return */ public static int Fibonacci2(int n, HashMap<Integer, Integer> map) { if (n == 0 || n == 1) { return n; } if (map.containskey (n)) {return map.get(n); } else { int value = Fibonacci2(n - 1, map) + Fibonacci2(n - 2, map); map.put(n, value); return value; }}Copy the code

4. Dynamic programming

  1. Determine the state transition equation (similar to a recursive formula)
  2. Dealing with boundary problems
  3. Find the optimal substructure of the equation
/ * * * < p > * * state transition equation using the dynamic programming way: F (n) = F (n - 1) + F (n + 1) * boundary: F (0) = 0. F(1) = 1 * optimal substructure: f(n-1) + f(n+1) * <p> * <p> * runtime: 12ms * Submitted by more than 5.06% in Java code 9720 KB * * * @ param @ return n * * / public static int Fibonacci3 (int n) {if (n = = 0 | | n = = 1) { return n; } int a = 0; int b = 1; int temp = 0; for (int i = 2; i < n + 1; i++) { temp = a + b; a = b; b = temp; } return temp; }Copy the code