💬 Discord
Sign In
NeetCode #659LC-1137Easy1-D Dynamic ProgrammingNC 250
← Back to All Problems

#659 · #1137 · N-th Tribonacci Number(第 N 个泰波那契数)

📌 Problem Statement & Constraints

The Tribonacci sequence is defined by T0 = 0, T1 = 1, T2 = 1, and Tn = Tn-1 + Tn-2 + Tn-3 for n >= 3. Given n, return Tn. Constraints: 0 <= n <= 37, and the answer fits in a 32-bit integer.

💡 Core Algorithmic Approaches

  1. Iterate forward, keeping the three most recent terms in rolling variables.
  2. Each new term is the sum of the previous three: a, b, c = b, c, a + b + c.
  3. Handle the base cases n = 0, n = 1, and n = 2 directly before the loop.
  4. With n <= 37 the direct iteration is trivially fast; matrix exponentiation would be overkill.

💻 Benchmark Python3 Implementation

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        a, b, c = 0, 1, 1              # T0, T1, T2
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c
        return c

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Getting the seeds wrong: the sequence starts 0, 1, 1, not 0, 0, 1.
  • Returning the wrong rolling variable: after the loop the current term is c.
  • Using plain recursion: it is exponential without memoisation, which is needless here.
  • Worrying about overflow: the constraint guarantees the result fits in 32 bits.