Room 04 · The Grind — 1-D Dynamic Programming

N-th Tribonacci Number

EASY✓ CHIP-TIMEDLC #1137 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: A sibling of Fibonacci where each term sums the three terms before it instead of two, seeded 0, 1, 1. Compute the n-th term of that sequence.

A sequence starts with the three seed values 0, 1, and 1, and every term after that is the sum of the three terms immediately before it — the same idea as Fibonacci, one term wider.

The task is to compute a single term of that sequence at a chosen position, counting the very first seed value as position zero.

position n is a small non-negative integer
sequence is seeded 0, 1, 1 at positions 0, 1, 2
each term is the sum of the three terms directly before it
answer fits within a standard 32-bit integer range

EX 01

n = 0

→ 0

seed value T0

EX 02

n = 1

→ 1

seed value T1

EX 03

n = 2

→ 1

seed value T2

The hintstake only what you need

HINT 1 THE NUDGE

The direct recursive definition — sum the previous three calls — recomputes the same small n's an exploding number of times. Which values does the very next term actually need?

HINT 2 THE STRUCTURE

Only the last three terms ever matter to produce the next one. Once a term is more than three steps behind, it's dead weight.

HINT 3 ONE STEP FROM THE ANSWER

Slide three variables forward: the new term is their sum, and the oldest of the three gets dropped. Seed with T0 = 0, T1 = 1, T2 = 1 and roll forward to n.

Coach's boardthe pattern, step by step

THE TRIPLE ROLLPATTERN · ROLLING TRIPLEn = 7 · sequence seeded 0, 1, 1

STEP 1

Seed the sequence with its three starting terms: T0 = 0, T1 = 1, T2 = 1.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/n-th-tribonacci-number.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1 or 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

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 10 LN

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1
        return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)

TIME O(3^N)SPACE O(N)PYTHON · TRAINING PACE · 7 LN

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

TIME O(N)SPACE O(1)JAVA · RACE PACE · 18 LN

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
}

TIME O(3^N)SPACE O(N)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED