Rust语言编程实例100题-056

题目：LeetCode 练习 1137. 第 N 个泰波那契数

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

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

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

程序分析：泰波那契数的边界条件是 T(0)=0, T(1)=1, T(2)=1T(0)=0,T(1)=1,T(2)=1。当 n>2n>2 时，每一项的和都等于前三项的和，因此有如下递推关系：

T(n)=T(n-1)+T(n-2)+T(n-3)
T(n)=T(n−1)+T(n−2)+T(n−3)

由于泰波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 T(0)T(0)、T(1)T(1) 和 T(2)T(2)。

知识点：动态规划

参考程序代码：

fn main() {
    let result = tribonacci(5);
    dbg!(result);
}

pub fn tribonacci(n: i32) -> i32 {
    if n == 0 {
        return 0;
    }
    if n == 1 || n == 2 {
        return 1;
    }

    let mut a = 0;
    let mut b = 1;
    let mut c = 1;
    let mut result = 0;

    for _ in 3..=n {
        result = a + b + c;
        a = b;
        b = c;
        c = result;
    }

    return result;
}

程序执行结果：

result = 7