The Tribonacci sequence T_n is defined as follows: 

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

Given an integer n, return the value of the n-th Tribonacci number 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 be a 32-bit integer, that is, answer <= 2^31 - 1.

Approach

#

By inspection, the problem asks us to compute a sequence in which each term is obtained from the previous three terms. Therefore, the simplest brute-force algorithm is sufficient.

We create an array with the three fixed values given in the problem, [0,1,1]. We then use the given n to compute terms until reaching the requested position, which gives us the n-th Tribonacci number.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn tribonacci(n: i32) -> i32 {
        let n = n as usize;
        let mut v = vec![0, 1, 1];
        let mut cur_len = 3;
        while cur_len <= n {
            v.push(v[cur_len - 1] + v[cur_len - 2] + v[cur_len - 3]);
            cur_len += 1;
        }
        v[n]
    }
}

Result

#

# fn main() {
# pub fn tribonacci(n: i32) -> i32 {
#    let n = n as usize;
#    let mut v = vec![0, 1, 1];
#    let mut cur_len = 3;
#    while cur_len <= n {
#        v.push(v[cur_len - 1] + v[cur_len - 2] + v[cur_len - 3]);
#        cur_len += 1;
#    }
#    v[n]
# }
println!("{:?}", tribonacci(2));
# }