本文共 1103 字，大约阅读时间需要 3 分钟。

递归法

原理： 把 f(n)f(n) 问题的计算拆分成 f(n-1)f(n−1) 和 f(n-2)f(n−2) 两个子问题的计算，并递归，以 f(0)f(0) 和 f(1)f(1) 为终止条件。

会导致超时，不可用。

记忆化递归法

原理： 在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 (n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。

新建一个数组，每次把计算出的值进行缓存，这样保证每个值只进行一次运算，已计算过的值就从缓存中读取。

class Solution {       int[] dp ;    public int fib(int n) {           init(n);        return compute(n);            }     public int compute(int n ){                   if(dp[n]!=-1){              //-1，表示尚未计算过，非-1，表示计算过，直接从缓存中读取即可            return dp[n];        }        int c= compute(n-1)+compute(n-2);                                 if(c>1000000007){                 c=  c%1000000007;            }            //加入缓存            dp[n] = c;            return c;             }    public void init(int n){                 dp =  new int[n+1];               if(n==0){              dp[0]=0;               return ;        }         for(int i =1;i<=n;i++){            //初始值为-1，表示未计算值           dp[i]=-1;       }                  dp[1]=1;                }}