泰波那契序列 T_n 定义如下： 

T₀ = 0, T₁ = 1, T₂ = 1, 且在 n >= 0 的条件下 T_n+3 = T_n + T_n+1 + T_n+2

给你整数 n，请返回第 n 个泰波那契数 T_n 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

思路分析

#

通过观察，发现题目要求的是一个数列的和。而且这个数列可以通过前面的3项来计算得到后面的一项。因此我们可以用最简单的暴力算法来做。 也就是我们新建一个数组，里面有固定的三项[0,1,1]。这是题目中给我们的条件，然后我们根据给入的n去计算到我们需要的地方，就可以获得第 N 个泰波那契数了

Rust代码

#

# 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]
    }
}

运行效果

#

# 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));
# }