题目：为什么下面第一种代码比第二种使用了 更小的内存，有无比这两种实现第 N 个泰波那契数更好的方法？

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;}}
}

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;}
}

解答：

• 第一种代码使用了 HashMap 来存储计算过的结果，避免了重复计算，可以减少内存的使用。
• 而第二种代码则只是使用了变量来保存每个数的值，没有进行任何缓存，所以在计算较大的n时会占用更多内存，
  因为需要保存所有之前的值才能继续计算。
• 所以第一种代码比第二种代码使用了更小的内存。

更优解：

另外可以尝试使用一个数组来保存每个数的值，这样就不用使用 HashMap 或者变量来存储计算过的结果了。这种方式比较简单，代码如下：

class Solution {public int tribonacci(int n) {if (n == 0) return 0;if (n <= 2) return 1;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];}
}

• 这段代码是一个求第n个Tribonacci数的算法实现。Tribonacci数列是类似于斐波那契数列的一种数列，其定义为：T(0) =
  0, T(1) = 1, T(2) = 1，对于 n > 2，有 T(n) = T(n - 1) + T(n - 2) + T(n -
  3)。
• 具体来说，该算法通过一个动态规划的思想来解决问题。首先，当 n = 0 时，结果直接返回0；当 n <= 2
  时，结果直接返回1。然后，对于大于2的情况，我们创建一个长度为 n+1 的数组 dp，其中dp[i] 表示第 i 个 Tribonacci
  数的值。接着，我们从 3 开始遍历到 n，用递推公式 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
  来计算每一个元素。最后返回 dp[n] 即可得到结果。

总结：

整个算法的时间复杂度为 O(n)，空间复杂度也为 O(n)，因为我们使用了一个额外的数组来存储中间结果。
这种实现方式的时间复杂度和空间复杂度都是 O(n)，因为需要保存所有之前的值才能继续计算。但是相比第一种代码，这种方式没有额外的 HashMap 开销，所以可能会稍微快一些。