Recursion_ Calculate f (n) =f (n-1) +f (n-2)

subject ：

1 、1、2、3、5、8.... Calculation 103 Value

law ：f(n)=f(n-1)+f(n-2)

Basic Edition ： Algorithm implementation

public static int getResult(int num){
    if (num<=2) return 1;
    return getResult(num - 1) + getResult(num - 2);
}

 Recursion of memo mode （ Cache the results of previous calculations to reduce the solution of overlapping subproblems ）O(N)：

private static final Map<Integer, Long> cache = new HashMap<>();
public static long getResult(int num){
    if (num<=2) return 1;
  return   cache.computeIfAbsent(num,k->getResult(num - 1) + getResult(num - 2)) ;
}

computeIfAbsent()  Method pair  hashMap  It is specified in  key  Recalculate the value of , If this doesn't exist  key, Add to  hashMap  in 

Dynamic programming method O(N)

public static int getResult2(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    int[] dp = new int[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

State compression O(1)

public static int getResult3(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) {
        return 1;
    }
    int prev = 1;
    int current = 2;
    for (int i = 3; i <= n; i++) {
        int sum = prev + current;
        prev = current;
        current = sum;
    }
    return current;
}