[leetcode 1137. N-th Tribonacci Number N번째 트리보나치 수] - DP

문제

트리보나치 수열 Tn 은 다음과 같이 정의됩니다. 

T 0 = 0, T 1 = 1, T 2 = 1, 그리고 T n+3 = T n + T n+1 + T n+2 for n >= 0.

가 주어지면 Tnn 값을 반환합니다 .

 

예시 1:

입력: n = 4

 출력: 4

 설명: 

T_3 = 0 + 1 + 1 = 2 

T_4 = 1 + 1 + 2 = 4

예 2:

입력: n = 25

 출력: 1389537

 

제약:

• 0 <= n <= 37
• 답은 32비트 정수 내에 들어맞는 것이 보장됩니다. answer <= 2^31 - 1.

코드

class Solution {
    int a[];
    public int tribonacci(int n) {
        a = new int[n+1];
        for(int i=0; i<=n; i++){
            a[i] = -1;
        }
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }else if(n == 2){
            return 1;
        }else{
            a[0] = 0;
            a[1] = 1;
            a[2] = 1;    
        }
        return dp(n);
    }
    public int dp(int n){
        if(a[n] != -1){
            return a[n];
        }
        return a[n] = dp(n-3)+dp(n-2)+dp(n-1);
    }

}