What is the best approach for solving N-th Tribonacci Number?

Use state transition dynamic programming with an array or rolling variables to compute each Tn iteratively and efficiently.

Can I solve it recursively without exceeding time limits?

Yes, but only with memoization. Plain recursion causes exponential time complexity and will likely fail for larger n.

What are the base cases for the Tribonacci sequence?

T0 = 0, T1 = 1, and T2 = 1. Correctly initializing these is critical to prevent off-by-one errors in your DP solution.

How much memory does the iterative approach use?

A full DP array uses O(n) space, but rolling three variables reduces space complexity to O(1) without affecting correctness.

Why is this considered state transition dynamic programming?

Because each state Tn is defined as a deterministic function of the previous three states, matching the classic DP pattern.

#1137

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

第 N 个泰波那契数

泰波那契序列 T n 定义如下： T 0 = 0, T 1 = 1, T 2 = 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…

数学动态规划记忆化

题目描述

泰波那契序列 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。

lightbulb

解题思路

方法一：动态规划

根据题目中给出的递推式，我们可以使用动态规划求解。

我们定义三个变量 $a$ , $b$ , $c$ ，分别表示 $T_{n-3}$ , $T_{n-2}$ , $T_{n-1}$ ，初始值分别为 $0$ , $1$ , $1$ 。

然后从 $n$ 减小到 $0$ ，每次更新 $a$ , $b$ , $c$ 的值，直到 $n$ 为 $0$ 时，答案即为 $a$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为给定的整数。

1

2

3

4

5

6

7

class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c = 0, 1, 1
        for _ in range(n):
            a, b, c = b, c, a + b + c
        return a

speed

复杂度分析

指标	值
时间	complexity is O(n) for both iterative and memoized approaches. Space complexity is O(n) for full DP arrays or O(1) for optimized rolling variables. Memoization avoids exponential recursion time, a key failure mode in naive recursion.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you can optimize space using only three variables instead of a full array.
question_mark
Expect discussion on the state transition formula Tn+3 = Tn + Tn+1 + Tn+2.
question_mark
Clarify handling of edge cases n = 0, 1, or 2 to ensure correct base initialization.

warning

常见陷阱

外企场景

error
Using naive recursion without memoization leads to exponential time complexity.
error
Failing to handle the initial base cases correctly can produce off-by-one errors.
error
Attempting to optimize prematurely without ensuring the DP state transition is correctly implemented.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the N-th Fibonacci number using a similar state transition DP approach as a simpler case.
arrow_right_alt
Modify the sequence to sum the previous four numbers and compute the N-th value, testing generalization.
arrow_right_alt
Implement a Tribonacci-like sequence starting with custom initial values, maintaining DP state transitions.

help

常见问题

外企场景

继续练习

#964 表示数字的最少运算符 #913 猫和老鼠 #1569 将子数组重新排序得到同一个二叉搜索树的方案数