剑指 Offer 10- I. 斐波那契数列

用哈希表

public int fib(int n) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,0);
        map.put(1,1);
        if(map.containsKey(n)){
            return map.get(n);
        }
        for(int i = 2;i<=n;i++){
            int k = (int)((map.get(i-2)+map.get(i-1))%(1e9+7));
            map.put(i,k);
        }
        return map.get(n);
    }