P1137

泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

这个比较简单,就是一个递归,但是运行的时候,会超时,原因是做了重复的运算,加一个缓存

 private Map<Integer, Integer> cache = new HashMap ();

    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        if (cache.containsKey(n)){
            return cache.get(n);
        }
        int i1 = tribonacci(n - 3);
        int i2 = tribonacci(n - 2);
        int i3 = tribonacci(n - 1);
        cache.put(n-3,i1);
        cache.put(n-2,i2);
        cache.put(n-1,i3);
        return i1+i2+i3;
    }