Skip to content

1137. N-th Tribonacci Number 👍

Approach 1: Straightforward

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int tribonacci(int n) {
    if (n < 2)
      return n;

    vector<int> dp{0, 1, 1};

    for (int i = 3; i <= n; ++i) {
      const int next = dp[0] + dp[1] + dp[2];
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = next;
    }

    return dp[2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int tribonacci(int n) {
    if (n < 2)
      return n;

    int[] dp = {0, 1, 1};

    for (int i = 3; i <= n; ++i) {
      final int next = dp[0] + dp[1] + dp[2];
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = next;
    }

    return dp[2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def tribonacci(self, n: int) -> int:
    if n < 2:
      return n

    dp = [0, 1, 1]

    for _ in range(3, n + 1):
      dp[0], dp[1], dp[2] = dp[1], dp[2], sum(dp)

    return dp[2]

Approach 2: Concise

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  int tribonacci(int n) {
    vector<int> dp{0, 1, 1};

    for (int i = 3; i <= n; ++i)
      dp[i % 3] = dp[0] + dp[1] + dp[2];

    return dp[n % 3];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public int tribonacci(int n) {
    int[] dp = {0, 1, 1};

    for (int i = 3; i <= n; ++i)
      dp[i % 3] = dp[0] + dp[1] + dp[2];

    return dp[n % 3];
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def tribonacci(self, n: int) -> int:
    dp = [0, 1, 1]

    for i in range(3, n + 1):
      dp[i % 3] = sum(dp)

    return dp[n % 3]