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

直接使用递归会超时，因为包含了太多的重复计算，为了减少重复计算，使用哈希表存储之前计算的结果，再次遇到直接查表就可以了。需要注意的是判断map中是否存在某一键返回布尔的方法是 containsKey() ；

class Solution {
       Map
   
     map = new HashMap<>();    public int fib(int n) {
           if(n<2){
               return n;        }        int res;        if(map.containsKey(n)){
               return map.get(n);        }else{
               res = (fib(n-1) + fib(n-2)) % 1000000007;            map.put(n,res);        }        return res;    }}
   

转载地址：http://qsozi.baihongyu.com/