Nth Tribonacci Number

easy dp recurrence

Problem

The tribonacci sequence is T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n−1) + T(n−2) + T(n−3). Compute T(n) using O(1) rolling state.

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;
}

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