README.md

1137. N-th Tribonacci Number

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

• 0 <= n <= 37
• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 231 - 1.

Solutions (Rust)

1. Recursion

impl Solution {
    pub fn tribonacci(n: i32) -> i32 {
        fn helper(n: usize) -> Vec<i32> {
            match n {
                0 => vec![0],
                1 => vec![0, 1],
                2 => vec![0, 1, 1],
                _ => {
                    let mut v = helper(n - 1);
                    let t_n = v[n - 3] + v[n - 2] + v[n - 1];
                    v.push(t_n);
                    v
                },
            }
        }
        let n = n as usize;
        helper(n)[n]
    }
}

2. Iteration

impl Solution {
    pub fn tribonacci(n: i32) -> i32 {
        match n {
            0 => 0,
            1 | 2 => 1,
            _ => {
                let mut t = (0, 1, 1);
                for i in 3..=n {
                    t = (t.1, t.2, t.0 + t.1 + t.2);
                }
                t.2
            },
        }
    }
}