題目說明：Tribonacci sequence 的定義如下:
T0=0, T1=1, T2=1, T3=T1+T2+T3,...,Tn+3=Tn+(Tn+1)+(Tn+2)

Case 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Case 2
Input: n = 25
Output: 1389537

解題思路:這題跟climbing stairs的概念十分相似，既然題目都幫我們列出遞迴式子，依照題意就可以使用dynamic programming進行解題。

附上程式碼
Java

class Solution {
    public int tribonacci(int n) {
       if(n == 0){
            return 0;
        }
        if(n<=2){
            return 1;
        }
        int dp[] = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3; i<=n; ++i){
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
}
}

Python

class Solution:
    def tribonacci(self, n: int) -> int:
        if n==0:
            return 0
        elif n==1 or n==2:
            return 1
        else:
            dp=[0,1,1]
            for i in range(3,n+1):
                dp.append(dp[i-1]+dp[i-2]+dp[i-3])
            return dp[n]