[LeetCode] 1137. N-th Tribonacci Number

1137. N-th Tribonacci Number

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.

 

 

My Code

class Solution:
    def tribonacci(self, n: int) -> int:
        if n<=1:
            return n
        elif n==2:
            return 1
            
        dp = [0] * (n+1)

        dp[0]=0
        dp[1]=1
        dp[2]=1
        for i in range(3, n+1):
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1]

        return dp[n]

 

 

Improved

class Solution:
    def tribonacci(self, n: int) -> int:
        if n==0:
            return 0
        elif n==1 or n==2:
            return 1

        t1, t2, t3 = 0, 1, 1
        for i in range(3, n+1):
            t = t1 + t2 + t3
            t1, t2, t3 = t2, t3, t
        return t

 

 

 

- Memory Efficiency : Instead of using an array, the optimized code uses only three variables, reducing the space complexity to O(1)

- Same Time Complexity: The time complexity remains O(n), ensuring no impact on preformance.