[leetcode] N-th Tribonacci Number

문제

• Tribonacci는 T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0으로 정의된다. 정수 n이 주어질 때, Tn을 구해야 한다.
• 제약 조건
  • n 범위: 0 <= n <= 37
  • 정답은 32 bit 정수 범위 안에 있다.

풀이

풀기 전

• 피보나치인데 계산하는 항이 하나 추가되었다. 피보나치 풀 듯이 풀면 된다.
• 한 번 계산한 결과는 저장한 뒤 필요할 때 사용해야 한다. 저장하지 않고 항상 계산하면 시간 복잡도가 매우 늘어난다.

코드

class Solution {
    private int[] results = new int[38];

    public int tribonacci(int n) {
        if (n == 0)
            return 0;
        if (n <= 2)
            return 1;
        
        if (results[n] == 0)
            results[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
            
        return results[n];
    }
}

푼 후

• 피보나치를 풀어봤다면 어렵지 않게 풀 수 있다.
• n보다 작은 값들을 한 번씩 계산하고 저장하여 사용하기 때문에 시간 복잡도는 O(n)이다. 재귀 깊이가 최대 n이기 때문에 공간 복잡도도 O(n)이다.