前言

September LeetCoding Challenge 2021今天的題目是1137. N-th Tribonacci Number，跟DP最基礎經典的費氏數列基本一樣，只是多一個數字，就當作複習寫寫看吧！

想法

我們在Day 4的時候就有提過費氏數列的解法。可以來回顧一下最費時的方式就是recursive，我要求t(10)的時候就讓他去呼叫t(9)+t(8)+t(7)，然後每個又回去呼叫本題，寫法如下：

class Solution {
public:
    int tribonacci(int n) {
        // use dp to save computed elements
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }
        
        return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
    }
};

可以跑跑看體會一下時間感XD n每+1，時間是n倍數的在增加。
而經典的DP寫法如下：

class Solution {
public:
    int tribonacci(int n) {
        // use dp to save computed elements
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }
        vector<int> tri(n+1,0);
        tri[1]=1;
        tri[2]=1;
        for(int i=3;i<=n;++i){
            tri[i]=tri[i-1]+tri[i-2]+tri[i-3];
        }
        return tri[n];
    }
};

我們也有提到過其實每次只需要前三個數字，那我們也不需要維護一個n+1這麼大的table，只要每次保留最新的三組就好，節省一些些空間，如下：

class Solution {
public:
    int tribonacci(int n) {
        // use dp to save computed elements
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }
        int t1=0;
        int t2=1;
        int t3=1;
        int ans=t1+t2+t3;
        for(int i=3;i<=n;++i){
            ans = t1+t2+t3;
            t1 = t2;
            t2 = t3;
            t3 = ans;
        }
        return ans;
    }
};

時間複雜度就是O(n)，因為從2~n我們每次會進行O(1)運算。

結語

今天的題目很簡單，就是DP系列的起點，還是要掌握好這個基本想法。