LeetCode——1137. 第 N 个泰波那契数(Java)

题目描述

题干:
泰波那契序列 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;
    }

总结

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

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

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


下一篇:什么是可重入锁