题目描述

题干：
泰波那契序列 Tn 定义如下： 
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

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

示例 2：
输入：n = 25
输出：1389537

题解思路

返回泰波那契序列的第n个数，一看这个函数就难免不让我觉得这时斐波那契数列的哥哥

首先我们难免想到的是递归实现，当然结果也是可以预料到的，超时

所以我们这里就不得不采用动态规划的思想，每次保存前三个数字的值，而不需要每次递归计算

正确代码

    // 递归超时
    public int tribonacci01(int n) {
        if (n == 0) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 1;
        else return tribonacci01(n - 1) + tribonacci01(n - 2) + tribonacci01(n - 3);
    }

    //dp
    public int tribonacci02(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int T0 = 0, T1 = 0, T2 = 1, ans = 1;
        for (int i = 3; i <= n; i++) {
            T0 = T1;
            T1 = T2;
            T2 = ans;
            ans = T0 + T1 + T2;
        }
        return ans;
    }

总结

我们总是感觉到递归的优雅，可是在性能方面真的是让人望而生畏

尤其工作后发现递归几乎不会出现，无论是他的易错还是性能都不允许我们使用

如果文章存在问题或者更好的题解，欢迎大家在评论区斧正和评论，各自努力，你我最高处见