[Leetcode] 1137. N-th Tribonacci Number

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.

 

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

 

이 문제는 피보나치를 이해하고 풀이를 했는가를 물어보기 위해 나온 문제인듯 하다 

원래 하던 피보나치 풀이에 숫자를 하나 더 더해주면 된다 

 

DP

var tribonacci = function(n) {
    const arr = new Array(n).fill(0);
    
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 1;
    arr[3] = 2;
    
    for (let i = 4; i < n + 1; i++) {
        arr[i] = arr[i -1] + arr[i -2] + arr[i - 3];
    }
    
    return arr[n];
};

 

recursive하게 풀이 하려면 이전글에 지금과 똑같이 해주면 된다 

 

Leetcode에 챌린지가 있길래 이번에 참여해봤다 

2개 참여해서 총 4문제 풀었는데 이제 슬슬 미디움에 도전할 때가 된 것 같다 

 

챌린지 참여하면서 미디움 도전해봐야지