Problem URL: N-th tribonacci number

This problem is just like fibonacci number, we will first solve it recursively and then memoize it to reduce redundant calculation.

class Solution:
    def tribonacci(self, n: int) -> int:
        def _tribonacci(n: int, memo: dict) -> int:
            if n in memo:
                return memo[n]

            if n == 0: return 0
            if n == 1 or n == 2: return 1

            memo[n] = _tribonacci(n-1, memo) + _tribonacci(n-2, memo) + _tribonacci(n-3, memo)
            return memo[n]

        return _tribonacci(n, {})

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