N-th Tribonacci Number

The task here is to find the n-th number in the Tribonacci sequence, which is a series where each number is the sum of the three preceding numbers, starting from 0, 1, and 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

        tribonacci_numbers = [0, 1, 1]

        for i in range(3, n + 1):
            tribonacci_numbers.append(tribonacci_numbers[i - 3] + tribonacci_numbers[i - 2] + tribonacci_numbers[i - 1])

        return tribonacci_numbers[n]

Explanation

• If n is 0, 1, or 2, we directly return the corresponding value from the sequence definition.
• We initialize a list with the first three Tribonacci numbers.
• Then, we use a for loop to calculate the Tribonacci numbers from the 3rd to the n-th number.
• We store the numbers in the list tribonacci_numbers so that we can reuse them in subsequent calculations.
• Finally, we return the n-th number from the list.

This approach ensures that we only calculate each Tribonacci number once and then store it for future use, leading to efficient computation.

title: N-th Tribonacci Number tags: recursion memoization

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

Constraints

• 0 <= n <= 37

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

Thinking Process

• Make an array F of length 38, and set F[0] = 0, F[1] = F[2] = 1.
• Now write a loop where you set F[n+3] = F[n] + F[n+1] + F[n+2], and return F[n].

Base cases

T0 = 0  for n = 0
T1 = 1  for n = 1
T2 = 1  for n = 2

Recurrence Relation

Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

T_3 = 0 + 1 + 1 = 2 n = 3
T_4 = 1 + 1 + 2 = 4 n = 4

1. Recursive approach. Base cases, recurrence relation.
2. Naive recursive approach: TLE
3. Memoize

Naive Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# @param {Integer} n
# @return {Integer}
def tribonacci(n)
  if n == 0
    return 0
  end
  if n <= 2
    return 1
  end
    
  tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)
end

Optimized Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# @param {Integer} n
# @return {Integer}
def tribonacci(n, memo={})
  if memo.key?(n)
    return memo[n]
  end
  
  if n == 0
    return 0
  end
  
  if n <= 2
    return 1
  end
    
  memo[n] = tribonacci(n-2, memo) + tribonacci(n-1, memo) + tribonacci(n-3, memo)
    
  memo[n]
end