DP

The Tribonacci sequence Tn is defined as follows: 

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

 

Example 1:

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

Input: n = 25
Output: 1389537

class Solution:
    def tribonacci(self, n: int) -> int:

        if n<3:
            if n==0 or n==1:
                return n
            else:
                return 1
            
        dp=[0]*(n+1)
        dp[0]=0
        dp[1]=1
        dp[2]=1  
        
        for i in range(3,len(dp)):
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        return dp[n]    

space=o(1)
class Solution:
    def tribonacci(self, n: int) -> int:

        if n<3:
            if n==0 or n==1:
                return n
            else:
                return 1
        a,b,c=0,1,1
        for i in range(3,n+1):
            d=a+b+c
            a,b,c=b,c,d
        return d