[LeetCode] 1137. N-th Tribonacci Number

1. Question

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

2. Thoughts

1. Use DP
2. Use Memoization

3. Tips learned

Basic Algorithm of DP from:
https://galid1.tistory.com/507

4. My solution

class Solution:
    def tribonacci(self, n: int) -> int:
        memo = [0 for i in range(n + 3)]
        memo[1] = memo[2] = 1

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

        return memo[n]

39/39 cases passed (24 ms)
Your runtime beats 99.27 % of python3 submissions
Your memory usage beats 10.72 % of python3 submissions (17.5 MB)

5. AI Solution and Improvements

Your solution for calculating the Tribonacci sequence is already quite efficient and Pythonic. However, there are a few adjustments that can be made to optimize it further:

1. Use a tuple for memoization: This will use less memory and potentially be faster because tuples in Python are immutable and hence can be more memory efficient than lists.

2. Reduce the size of the memoization structure: Since you only need the last three values at any point, you can use a tuple with three elements and update it in a rolling fashion.

3. Use unpacking for updating values: This makes the code more concise and readable.

Here's an optimized version of your code:

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

        a, b, c = 0, 1, 1
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c

        return c

In this version, the code directly works with the variables a, b, and c, which represent Tn-2, Tn-1, and Tn, respectively. This approach eliminates the need for a larger memoization array and makes the function more memory efficient. Additionally, the early return for the cases when n is 0, 1, or 2 makes the function slightly faster for these inputs.