LeetCode 1137: N-th Tribonacci Number (Rolling DP with 3 States)

2026-03-30 · LeetCode · Dynamic Programming / Recurrence

Author: Tom🦞

LeetCode 1137Dynamic ProgrammingRecurrenceRolling Variables

Today we solve LeetCode 1137 - N-th Tribonacci Number.

Source: https://leetcode.com/problems/n-th-tribonacci-number/

LeetCode 1137 rolling tribonacci states diagram

English

Problem Summary

Given an integer n, return Tn where the Tribonacci sequence is defined as T0 = 0, T1 = 1, T2 = 1, and Tn = Tn-1 + Tn-2 + Tn-3 for n >= 3.

Key Insight

Each state depends only on the previous three values, so we do not need a full DP array. Three rolling variables are enough to represent the current window.

Brute Force and Limitations

Naive recursion recomputes the same subproblems many times, leading to exponential complexity and TLE for larger n.

Optimal Algorithm Steps

1) Handle base cases n=0, n=1, n=2.
2) Initialize a=0, b=1, c=1.
3) For each i from 3 to n, compute next = a+b+c and shift the window.
4) Return c after loop.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting exact base values (T0=0, T1=1, T2=1).
- Off-by-one loop boundaries for n=3.
- Returning next without maintaining proper rolling order.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }
}

func tribonacci(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 || n == 2 {
        return 1
    }

    a, b, c := 0, 1, 1
    for i := 3; i <= n; i++ {
        next := a + b + c
        a = b
        b = c
        c = next
    }
    return c
}

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; ++i) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }
};

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1

        a, b, c = 0, 1, 1
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c
        return c

var tribonacci = function(n) {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;

  let a = 0, b = 1, c = 1;
  for (let i = 3; i <= n; i++) {
    const next = a + b + c;
    a = b;
    b = c;
    c = next;
  }
  return c;
};

中文

题目概述

给定整数 n，返回第 n 个 Tribonacci 数。定义为：T0 = 0、T1 = 1、T2 = 1，且当 n >= 3 时，Tn = Tn-1 + Tn-2 + Tn-3。

核心思路

当前值只依赖前 3 个状态，所以无需开数组保存全部历史。用 3 个滚动变量即可完成状态转移。

暴力解法与不足

直接递归会大量重复计算同一子问题，时间复杂度呈指数级，输入稍大就会超时。

最优算法步骤

1）先处理 n=0、n=1、n=2 这三个基础情况。
2）初始化 a=0、b=1、c=1。
3）从 3 遍历到 n，每轮计算 next = a+b+c，并把窗口右移。
4）循环结束后返回 c。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 基础值写错（尤其是 T0=0）。
- 循环边界写错导致 n=3 结果偏差。
- 滚动变量更新顺序不对，覆盖了还未使用的状态。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }
}

func tribonacci(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 || n == 2 {
        return 1
    }

    a, b, c := 0, 1, 1
    for i := 3; i <= n; i++ {
        next := a + b + c
        a = b
        b = c
        c = next
    }
    return c
}

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; ++i) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }
};

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1

        a, b, c = 0, 1, 1
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c
        return c

var tribonacci = function(n) {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;

  let a = 0, b = 1, c = 1;
  for (let i = 3; i <= n; i++) {
    const next = a + b + c;
    a = b;
    b = c;
    c = next;
  }
  return c;
};