Leetcode 1137. N-th Tribonacci Number

Problem

Leetcode 1137 - N-th Tribonacci Number

Example:

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

Input: n = 25
Output: 1389537

Approach

Using array, we can store the all previous values. For example, we can save T_0, T_1, T_2. With the information, we can calculate T_3, T_4, and up to T_n in the saved array.

Thus we can return T_n at the end

Here is the Python code for the solution:

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

        return dp[-1]

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$