[leetcode #1137] N-th Tribonacci Number

Problem

The Tribonacci sequence Tn is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂ for n >= 0.

Given n, return the value of Tₙ.

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.

Idea

피보나치 수열이 아닌 트리보나치 수열의 값을 구하는 문제다. 피보나치 수열을 푸는 가장 간단한 방법은 재귀 함수를 이용하는 것이다. 하지만 여기서 n이 37일 때도 답을 구해야 하므로 재귀 함수를 이용해 풀면 Time Limit Exceeded가 발생한다. 재귀 함수를 이용하는 것보다 더 효율적으로 문제를 푸는 건 dp를 이용하는 것이다. 주어진 정수 n에 도달할 때까지 n보다 작은 트리보나치 수열 값을 저장하는 방식으로 문제를 푼다.

알고리즘은 다음과 같다.

1. n이 0일 때는 0을, 1이나 2일 때는 1을 리턴한다.
2. n이 3보다 클 경우 Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂ 식을 적용해 트리보나치 수열 값을 차례로 구한다.
3. n일 때의 트리보나치 수열 값을 리턴한다.

Solution

class Solution {
    int[] dp = new int[38];

    public int tribonacci(int n) {
        if (n == 0)
            return 0;

        if (n == 1 || n == 2) 
            return 1;

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        int i=3;
        while (i <= n) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
            i++;
        }

        return dp[n];
    }
}

Reference

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