這是小川的第409次更新，第441篇原創(chuàng)
看題和準備
今天介紹的是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位整數(shù)蛔六，即 答案 <= 231 - 1。
第一種解法
泰波那契废亭，和斐波那契數(shù)列相似国章，只是比斐波那契數(shù)列多了一項，后一項的值為前三項的值之和豆村。
暴力解法液兽，直接使用遞歸，會超時掌动。
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更大時，重復的計算會嚴重影響代碼計算速度凭迹。
我們可以使用數(shù)組罚屋，將每一步的計算結果都保存起來，當新的一項需要前面三項的計算結果時嗅绸，可以直接從數(shù)組中取脾猛，減少不必要的重復計算。
此解法的時間復雜度是O(N)鱼鸠，空間復雜度為O(N)猛拴，使用了一個容量為n+1的數(shù)組羹铅。
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];
}
第三種解法
在第二種解法的基礎上，我們還可以繼續(xù)優(yōu)化愉昆。
泰波那契數(shù)列中职员，新的一項需要借助前三項的值得到，例如T(6) = T(5)+T(4)+T(3)跛溉，在第二種解法中焊切，我們卻將T(0)、T(1)芳室、T(2)的值都存起來了专肪，但是計算T(6)又用不到T(0)、T(1)堪侯、T(2)嚎尤，浪費了存儲空間。對此抖格，我們可以使用局部變量替換數(shù)組诺苹，只保留前三項的值，每次計算完新的一項值后雹拄，更新一次前三項的值即可收奔。
此解法的時間復雜度是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+篇，公眾號對話框回復【數(shù)據結構與算法】势篡、【算法】翩肌、【數(shù)據結構】中的任一關鍵詞，獲取系列文章合集禁悠。
以上就是全部內容念祭，如果大家有什么好的解法思路、建議或者其他問題碍侦，可以下方留言交流粱坤，點贊、留言瓷产、轉發(fā)就是對我最大的回報和支持站玄！
