Leetcode 1137 - N-th Tribonacci Number

Problem Description

The Tribonacci sequence Tn 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 \geq 0$.

Given $n$, return the value of $T_n$.

Examples

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

Thought Process / Intuition

Bottom up dynamic programming, returning the last item in the dp array.

Approach

1. Create a dp array of length n + 1, where the value at the $i-th$ index of the array is the value of $T_1$.
2. Initialize the zeroth, first and second values of the dp array to 0, 1 and 1 respectively, since we are given $T_0 = 0, T_1 = 1, T_2 = 1$
3. Iterate from the 3 to n, calculating and storing the $T_i$ in the dp array
4. Return the last item in the dp array.

Solution

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        if 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-1] + dp[i-2] + dp[i-3]
        return dp[n] 

Complexity Analysis

Time complexity: $O(n)$

For loop is length $O(n)$.

• Space complexity: $O(n)$

Space complexity: $O(n)$

Size of the DP array is $O(n)$.

Shoutout to My Friends' Solutions

Kurt's Solution

Si Yuan's Solution

My Solution on Leetcode