:-: 4.6 第N个泰波那契数 ***** **题干：** 泰波那契序列 Tn 定义如下：  T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。 示例 1： ~~~ 输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 ~~~ 示例 2： ~~~ 输入：n = 25 输出：1389537 ~~~ 提示： ~~~ 0 <= n <= 37 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。 ~~~ **题目分析：** 此题不难，简单的动态规划即可，基本方程式都给出来了。 **新手有可能遇到的解题思路陷阱：** 需注意的一点就是要节省空间资源，避免使用递归，进行重复计算。 **解题思路分析以及代码实现：** 第一种思路：动态规划。 第一种思路代码： ~~~ public static int tribonacci(int n) { int[] number = new int[n + 1]; //默认值都为0 number[1] = 1; number[2] = 1; if (n < 3) return number[n]; else { for (int i = 3; i <= n; i++) { number[i] = number[i - 1] + number[i - 2] + number[i - 3]; } } return number[n]; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：动态规划，不保存中间值。 第二种思路代码： ~~~ public static int tribonacci(int n) { if (n == 0) return 0; if (n == 1 || n == 2) return 1; int zero = 0, one = 1, two = 1; int sum = 0; for (int i = 3; i <= n; i++) { sum = zero + one + two; zero = one; one = two; two = sum; } return sum; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**