java 第 N 个泰波那契数

Question

在力扣提交第 N 个泰波那契数的时候 为什么第一种代码比 第二种使用了 更小的内存 不理解

1.

class Solution {
    HashMap<Integer,Integer> val= new  HashMap<Integer,Integer>();
    public int tribonacci(int n) {

        if(n==0){
            return 0;
        }
        if(n<=2){
            return 1;
        }
        if (val.containsKey(n)) {
            return val.get(n);
        }else{
            int a =  tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
            val.put(n,a);
            return a;
        }
        
    }
}

2.

class Solution {

    public int tribonacci(int n) {

        int a =0;
        int b=1;
        int c= 1;

        if(n==0){
            return 0;
        }
        if(n<=2){
            return 1;
        }
        for(int i =3;i<=n;i++){
            a=a+b+c;
            b=b^c;
            c=b^c;
            b=b^c;
            a=a^c;
            c=a^c;
            a=a^c;
        }
        return c;
    }
}

Answer 1

第一种和第二种比并不节约内存
只是HashMap<Integer,Integer> val= new  HashMap<Integer,Integer>();
的存在，和不用它缓存已经算出的结果的传统递归比，节约了内存。