题目链接
    image.png
    image.png
    image.png
    image.png

    1. class Solution {
    2.     public int fib(int n) {
    3.         // int[] arr = new int[n+1];
    4.         // return calculate1(n);
    5.         //  return calculate2(n,arr);
    6.           return calculate3(n);
    7.     }
    10.     // 1.暴力递归
    11.     public int calculate1(int n) {
    12.         if(n == 0 || n == 1) return n;
    14.         return calculate1(n-1)+calculate1(n-2);
    16.     }
    18.     // 2.去重递归
    19.       public int calculate2(int n,int[] arr) {
    20.         if(n == 0 || n == 1) return n;
    22.         if(arr[n] != 0) return arr[n];
    24.         arr[n] =  calculate2(n-1,arr)+calculate2(n-2,arr);
    25.         return arr[n];
    26.     }
    29.     // 3.双指针迭代，O(N)复杂度
    30.     public int calculate3(int n) {
    31.         int prev = 0;
    32.         int cur = 1;
    33.         for(int i = 0; i < n; i++) {
    34.             cur = prev+cur;
    35.             prev = cur-prev; 
    36.         }    
    37.         return prev;  // 返回prev是因为从0开始。
    38.     }
    40. }