Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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
      }
    }
  }
}