1137. N-th Tribonacci Number

Description

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:

• Input: n = 4
• Output: 4
• Explanation:
  T_3 = 0 + 1 + 1 = 2
  T_4 = 1 + 1 + 2 = 4

Example 2:

• Input: n = 25
• Output: 1389537

Constraints:

• 0 <= n <= 37
• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2³¹ - 1.

💡 Hint 1:
Make an array F of length 38, and set F[0] = 0, F[1] = F[2] = 1.

💡 Hint 2:
Now write a loop where you set F[n+3] = F[n] + F[n+1] + F[n+2], and return F[n].

Submitted Code

class Solution:
    def tribonacci(self, n: int) -> int:
        memo = [0] * 38
        memo[0], memo[1], memo[2] = 0, 1, 1

        for i in range(3, n+1):
              memo[i] = memo[i-3] + memo[i-2] + memo[i-1]

        return memo[n]

Runtime: 0 ms | Beats 100.00%
Memory: 17.12 MB | Beats 98.26%

앞 숫자들의 계산 결과를 리스트에 저장했다.

Other Solutions

1st

class Solution:
    def tribonacci(self, n):
        dp = [0, 1, 1]
        for i in xrange(3, n + 1):
            dp[i % 3] = sum(dp)
        return dp[n % 3]

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

이전 값 3개만 저장하면 되기 때문에 메모이제이션 없이 공간을 최적화하는 것도 좋은 방법이다.