LeetCode、1137. 第 N 个泰波那契数【简单，动态规划】-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode、1137. 第 N 个泰波那契数【简单，动态规划】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引：博客目录索引(持续更新)

视频平台：b站-Coder长路

LeetCode、1137. 第 N 个泰波那契数【简单，动态规划】

题目与分类

题目链接：LeetCode、1137. 第 N 个泰波那契数【简单，动态规划】

题目分类：动态规划/线性DP（一维DP）

思路

一维数组

递推公式：dp(i) = dp(i - 1) + dp(i - 2) + dp(i - 3) ，条件i >=3

一维动态规划

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

class Solution {
    
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[] tri = new int[n + 1];
        tri[0] = 0;
        tri[1] = 1;
        tri[2] = 1;
        for (int i = 3; i <= n; i ++) {
            tri[i] = tri[i - 1] + tri[i - 2] + tri[i - 3];
        }
        return tri[n];
    }
}