LeetCode 1137: N-th Tribonacci Number (Iterative DP)

2026-04-29 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 1137DPMath

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

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

LeetCode 1137 tribonacci recurrence transition diagram

English

Problem Summary

Given n, return the n-th Tribonacci number where T0=0, T1=1, T2=1, and Tn = Tn-1 + Tn-2 + Tn-3 for n >= 3.

Key Insight

Each state only depends on the previous three states, so we do not need an array. Keep three rolling values and update them in one pass.

Algorithm

- Handle base cases n=0,1,2.
- Maintain a=T0, b=T1, c=T2.
- For each i from 3 to n, compute next=a+b+c, then shift a=b, b=c, c=next.

Complexity Analysis

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

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

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (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 <= 2 { return 1 }
    a, b, c := 0, 1, 1
    for i := 3; i <= n; i++ {
        next := a + b + c
        a, b, c = b, c, next
    }
    return c
}

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (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 <= 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

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function(n) {
  if (n === 0) return 0;
  if (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 个泰波那契数。定义为 T0=0、T1=1、T2=1，且 Tn = Tn-1 + Tn-2 + Tn-3（n >= 3）。

核心思路

当前项只依赖前三项，因此不需要完整 DP 数组。用三个滚动变量即可。

算法步骤

- 先处理 n=0,1,2 的边界。
- 维护 a,b,c 分别表示最近三个状态。
- 循环计算 next=a+b+c 并滚动更新。

复杂度分析

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

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

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (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 <= 2 { return 1 }
    a, b, c := 0, 1, 1
    for i := 3; i <= n; i++ {
        next := a + b + c
        a, b, c = b, c, next
    }
    return c
}

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (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 <= 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

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function(n) {
  if (n === 0) return 0;
  if (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;
};