#1137
Easy Algorithms N th tribonacci number
Math Dynamic Programming Memoization
63.3% acceptance
Feb 25, 2026
4802
211
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.
Solution
Rust
Time O(n)
Space O(1)
impl Solution {
pub fn tribonacci(n: i32) -> i32 {
match n {
0 => 0,
1 | 2 => 1,
_ => {
let (mut a, mut b, mut c) = (0i32, 1i32, 1i32);
for _ in 3..=n {
let d = a + b + c;
a = b; b = c; c = d;
}
c
}
}
}
}