1137.N-th_Tribonacci_Number(Easy).md

1137. N-th Tribonacci Number (Easy)

Date and Time: Aug 22, 2024, 17:20 (EST)

Link: https://leetcode.com/problems/n-th-tribonacci-number/

Question:

The Tribonacci sequence $T_n$ is defined as follows:

$T_0 = 0, T_1 = 1, T_2 = 1$, and $T_{n+3} = T_n + T_{n+1} + T_{n+2}$ for n >= 0.

Given n, return the value of $T_n$.

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

Constraints:

• 0 <= n <= 37

• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Walk-through:

Similar to fibonacci number, we first store the base case dp = [0, 1, 1], then we repeatly append dp with dp[i-1] + dp[i-2] + dp[i-3] for range(3, n+1). And we return dp[n].

Python 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):
            dp.append(dp[i-3] + dp[i-2] + dp[i-1])
        return dp[n]

Time Complexity: $O(n)$
Space Complexity: $O(n)$