[LeetCode] 1137. N-th Tribonacci Number

 

https://leetcode.com/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&id=dynamic-programming 

N-th Tribonacci Number - LeetCode

문제 유형 : 다이나믹 프로그래밍

난이도 : Easy

 

문제

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

 

피보나치의 변형인 삼보나치(?)수열이다.

 

입력

n(0 <= n <= 37)이 주어진다.

 

출력

삼보나치 수의 값을 반환한다.

 

아이디어

피보나치수열의 구현과 비슷하다. 지난 2개에서 3개를 더하는 것 뿐이다.

 

코드(C++)

class Solution {
int cache[38];
public:
    Solution(){
        memset(cache, -1, sizeof(cache));
    }
    int tribonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        if(cache[n] != -1){
            return cache[n];
        }
        else{
            cache[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
            return cache[n];
        }
    }
};