N-th Tribonacci Number

easy dp recurrence

Problem

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.

Inputn = 6

Output13

0,1,1,2,4,7,13.

def tribonacci(n):
    if n < 2: return n
    a, b, c = 0, 1, 1
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c
    return c

function tribonacci(n) {
  if (n < 2) return n;
  let a = 0, b = 1, c = 1;
  for (let i = 3; i <= n; i++) {
    const d = a + b + c;
    a = b; b = c; c = d;
  }
  return c;
}

class Solution {
    public int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int d = a + b + c;
            a = b; b = c; c = d;
        }
        return c;
    }
}

int tribonacci(int n) {
    if (n < 2) return n;
    int a = 0, b = 1, c = 1;
    for (int i = 3; i <= n; i++) {
        int d = a + b + c;
        a = b; b = c; c = d;
    }
    return c;
}

Explanation

The Tribonacci sequence is like Fibonacci but each term is the sum of the previous three terms instead of two. To find T(n) we don't need a whole array — we just need to remember the last three values and roll them forward.

We start with the three known base values a, b, c = 0, 1, 1 (that is T(0), T(1), T(2)). The tiny shortcuts at the top handle n < 2 directly.

Then we loop from 3 up to n. Each step computes the next value as a + b + c and slides the window: the old b becomes the new a, the old c becomes the new b, and the freshly computed sum becomes the new c.

Example: for n = 6 the values march along as 0, 1, 1, 2, 4, 7, 13, so c ends at 13, which is the answer.

Because we only ever keep three numbers, this uses constant memory and finishes in a single linear pass.

Time: O(n) Space: O(1)