這是小川的第409次更新，第441篇原創(chuàng)

看題和準(zhǔn)備

今天介紹的是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);
}

第二種解法

在第一種解法中，使用了遞歸，雖然代碼變簡單了，但是多了許多重復(fù)計算，比如T(4) = T(3)+T(2)+T(1) = T(0)+T(1)+T(2)+T(2)+T(1)，只是計算n為4時，就計算了兩次n為0和n為1，當(dāng)n更大時，重復(fù)的計算會嚴(yán)重影響代碼計算速度。

我們可以使用數(shù)組，將每一步的計算結(jié)果都保存起來，當(dāng)新的一項需要前面三項的計算結(jié)果時，可以直接從數(shù)組中取，減少不必要的重復(fù)計算。

此解法的時間復(fù)雜度是O(N)，空間復(fù)雜度為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];
}

第三種解法

在第二種解法的基礎(chǔ)上，我們還可以繼續(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)，浪費(fèi)了存儲空間。對此，我們可以使用局部變量替換數(shù)組，只保留前三項的值，每次計算完新的一項值后，更新一次前三項的值即可。

此解法的時間復(fù)雜度是O(N)，空間復(fù)雜度為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;
}

小結(jié)

算法專題目前已更新LeetCode算法題文章266+篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對我最大的回報和支持！