这是小川的第409次更新，第441篇原创
看题和准备
今天介绍的是LeetCode算法题中Easy级别的第260题（顺位题号是1137）。Tribonacci(泰波那契)序列Tn定义如下：
对于n> = 0，T0 = 0，T1 = 1，T2 = 1，并且T(n+3) = T(n) + T(n+1) + T(n+2)。
给定n，返回Tn的值。
例如：
输入：n = 4
输出：4
说明：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
输入：n = 25
输出：1389537
注意：
0 <= n <= 37
答案保证小于32位整数，即 答案 <= 231 - 1。
第一种解法
泰波那契，和斐波那契数列相似，只是比斐波那契数列多了一项，后一项的值为前三项的值之和。
暴力解法，直接使用递归，会超时。
public int tribonacci(int n) {
if (n <= 2) {
return n == 0 ? 0 : 1;
}
return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
}第二种解法
在第一种解法中，使用了递归，虽然代码变简单了，但是多了许多重复计算，比如T(4) = T(3)+T(2)+T(1) = T(0)+T(1)+T(2)+T(2)+T(1)，只是计算n为4时，就计算了两次n为0和n为1，当n更大时，重复的计算会严重影响代码计算速度。
我们可以使用数组，将每一步的计算结果都保存起来，当新的一项需要前面三项的计算结果时，可以直接从数组中取，减少不必要的重复计算。
此解法的时间复杂度是O(N)，空间复杂度为O(N)，使用了一个容量为n+1的数组。
public int tribonacci2(int n) {
if (n <= 2) {
return n == 0 ? 0 : 1;
}
int[] arr = new int[n+1];
arr[1] = arr[2] = 1;
for (int i=3, len=arr.length; i<len; i++) {
arr[i] = arr[i-1]+arr[i-2]+arr[i-3];
}
return arr[n];
}第三种解法
在第二种解法的基础上，我们还可以继续优化。
泰波那契数列中，新的一项需要借助前三项的值得到，例如T(6) = T(5)+T(4)+T(3)，在第二种解法中，我们却将T(0)、T(1)、T(2)的值都存起来了，但是计算T(6)又用不到T(0)、T(1)、T(2)，浪费了存储空间。对此，我们可以使用局部变量替换数组，只保留前三项的值，每次计算完新的一项值后，更新一次前三项的值即可。
此解法的时间复杂度是O(N)，空间复杂度为O(1)，只使用了4个局部变量。
public int tribonacci3(int n) {
if (n <= 2) {
return n == 0 ? 0 : 1;
}
int T0 = 0, T1 = 1, T2 = 1;
int temp = 0;
for (int i=3; i<n+1; i++) {
temp = T0 + T1 + T2;
T0 = T1;
T1 = T2;
T2 = temp;
}
return temp;
}小结
算法专题目前已更新LeetCode算法题文章266+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
