Skip to content

1137. N-th Tribonacci Number

On LeetCode ->

Problem

Given \(T_0 = 0\), \(T_1 = T_2 = 1\), and \(T_n = T_{n-1} + T_{n-2} + T_{n-3}\), return \(T_n\).

Input: n = 4
Sequence: 0, 1, 1, 2, 4
Output: 4

Key trick

Keep only the last three values and update them simultaneously; storing the entire sequence is unnecessary.

Trap

  • Mishandling \(n = 0\), \(n = 1\), or \(n = 2\).
  • Updating variables one at a time and accidentally using an already-updated value.
  • Using naive recursion, which repeats work exponentially.

Why is it interesting?

It is a simple dynamic programming problem that demonstrates how fixed-width state can reduce space from \(O(n)\) to \(O(1)\).

Python solution

class Solution:
    def tribonacci(self, n: int) -> int:
        # After each iteration, shift the three-value window forward.
        prev3, prev2, prev1 = 0, 1, 1
        for _ in range(n):
            prev3, prev2, prev1 = prev2, prev1, prev3 + prev2 + prev1
        return prev3
  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)

Comment on my solution

Your solution is correct, idiomatic, and optimal. Parallel assignment safely shifts the rolling state, and iterating exactly n times makes prev3 equal to \(T_n\), including all base cases.

class Solution:
    def tribonacci(self, n: int) -> int:
        prev3, prev2, prev1 = 0, 1, 1
        for _ in range(n):
            prev3, prev2, prev1 = prev2, prev1, prev3 + prev2 + prev1
        return prev3